rgray@CS.UTK.EDU (Bob Vozner) (02/09/91)
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.