home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / theory / 1682 < prev    next >
Encoding:
Text File  |  1992-07-23  |  939 b   |  25 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!utcsri!torn!watserv1!watmath!neumann.waterloo.edu!alopez-o
  3. From: alopez-o@neumann.waterloo.edu (Alex Lopez-Ortiz)
  4. Subject: Lower bound independence
  5. Message-ID: <1992Jul23.204321.4615@math.waterloo.edu>
  6. Keywords: NP, independence
  7. Sender: news@math.waterloo.edu (News Owner)
  8. Organization: University of Waterloo
  9. Date: Thu, 23 Jul 1992 20:43:21 GMT
  10. Lines: 13
  11.  
  12. I recall reading about a proof that there exists a problem of complexity 
  13. n^2 for which only an exponential lower bound could ever be proven 
  14. within some formal system. Iread the note in a survey.
  15.  
  16. Does anybody knows the reference, either to the survey or the original
  17. paper where this was proven.
  18.  
  19. Alex L-0.
  20.  
  21. -- 
  22. Alex Lopez-Ortiz                              alopez-o@maytag.UWaterloo.ca
  23. Deparment of Computer Science                       University of Waterloo
  24. Waterloo, Ontario                                                   Canada
  25.