home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / theory / 1686 < prev    next >
Encoding:
Internet Message Format  |  1992-07-24  |  1.3 KB
  1. Path: sparky!uunet!stanford.edu!rutgers!rochester!fulk
  2. From: fulk@cs.rochester.edu (Mark Fulk)
  3. Newsgroups: comp.theory
  4. Subject: Re: Lower bound independence
  5. Keywords: NP, independence
  6. Message-ID: <1992Jul24.155959.26446@cs.rochester.edu>
  7. Date: 24 Jul 92 15:59:59 GMT
  8. References: <1992Jul23.204321.4615@math.waterloo.edu>
  9. Organization: Computer Science Department University of Rochester
  10. Lines: 17
  11.  
  12. In article <1992Jul23.204321.4615@math.waterloo.edu> alopez-o@neumann.waterloo.edu (Alex Lopez-Ortiz) writes:
  13. >I recall reading about a proof that there exists a problem of complexity 
  14. >n^2 for which only an exponential lower bound could ever be proven 
  15. >within some formal system. Iread the note in a survey.
  16.  
  17. You clearly have this wrong, since an n^2 problem could not have an
  18. exponential lower bound.  I suspect that you are referring to work
  19. of Case and Royer, which shows the existence, for any reasonable formal
  20. system F, of a problem that is in linear time, provable in F to be in
  21. quadratic time (a clocked TM is supplied), but not provable in F to be
  22. in linear time.  The proof is a fairly straightforward diagonalization.
  23. For details and references, you might email royer@top.cis.syr.edu
  24.  
  25. Mark
  26. -- 
  27. Mark A. Fulk            University of Rochester
  28. Computer Science Department    fulk@cs.rochester.edu
  29.