[comp.theory] Strongest Lower Bound for NP-Complete Problems

rgray@CS.UTK.EDU ("Robert J. Gray") (02/01/91)

   Hi.  Right now I am working on a paper, and I am looking for
information about the proven lower bound on the time complexity of NP-
Complete problems.  I have a paper from 1977 by Wolfgang Paul
called "A 2.5n Lower Bound on the Combinational Complexity of
Booleans Functions".  Do any of you know of any more recent work
where a stonger lower bound was proven than 2.5n?  I would be happy
to send my papers when they are completed.  Thank you.
			  -Robert J. Gray