Article: 2644 of comp.theory Path: o.gp.cs.cmu.edu!pt.cs.cmu.edu!rochester!uhura.cc.rochester.edu!ub!zaphod.mps.ohio-state.edu!magnus.ircc.ohio-state.edu!tut.cis.ohio-state.edu!ucbvax!CS.UTK.EDU!rgray From: rgray@CS.UTK.EDU (Bob Vozner) Newsgroups: comp.theory Subject: Thank You All for the Information Message-ID: <9102072137.AA28500@hydra2c.cs.utk.edu> Date: 8 Feb 91 17:19:50 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: Bob Vozner Lines: 52 I recently requested information from the network concerning the lower bound on NP-Complete Problems. I got many very good responses. Here is a list of the references I received. -Bob Vozner (formerly Gray) Allen Van Gelder, (I&C 79(1):1-21 (1988)) - Upper bound on NP-Complete Problems Blum, Norbert. "A Boolean Function Requiring 3n Network Size", Theoretical Computer Science 28 (1984) pp 337-345. Paul, W.J., "A 2.5n Lower Bound on the Combinational Complexity of Boolean Functions", SIAM J. Comp., Vol 6., (1977), No. 3, p 427-443. Stockmeyer, L., "On the combinational Complexity of Certain Symmetric Boolean Functions", Mathematical Systems Theory, Vol 10 (1977) p 323-336. Zwick, U., "A 4n Lower Bound on the Combinational Complexity over U_2 = B_2 of Certain Symmetric Boolean Function", TR 116/1988, The Moise and Frida Institute of Computer Science, Tel Aviv University. A. E. Andreev, "On a method for Obtaining More Than Quadratic Lower Bounds for the Complexity of PI-schemes. Neciporcuk, E.I., "A Boolean Function", Soviet Mathematics Doklady 7:4, 99-1000. Wegner, I., "The Complexity of Boolean Functions", John Wiley & Sons. Boppana, R., and Sipser, M., Handbook of Theoretical Computer Science. Schnorr, "A 3n Lower Bound on the Network Complexity of Boolean Function", Theoretical Computer Science 10 (1980) pp 83-92.