Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!pacbell.com!ucsd!ucbvax!CS.UTK.EDU!rgray
From: rgray@CS.UTK.EDU ("Robert J. Gray")
Newsgroups: comp.theory
Subject: Strongest Lower Bound for NP-Complete Problems
Message-ID: <9101302136.AA08524@hydra1c.cs.utk.edu>
Date: 1 Feb 91 15:30:02 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: "Robert J. Gray" <rgray%cs.utk.edu@VM1.NoDak.EDU>
Lines: 9


   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