home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / theory / 1689 < prev    next >
Encoding:
Text File  |  1992-07-25  |  1.8 KB  |  40 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!cs.utexas.edu!torn!watserv1!watmath!neumann.waterloo.edu!alopez-o
  3. From: alopez-o@neumann.waterloo.edu (Alex Lopez-Ortiz)
  4. Subject: Re: Lower bound independence
  5. Message-ID: <1992Jul24.182855.25240@math.waterloo.edu>
  6. Keywords: NP, independence
  7. Sender: news@math.waterloo.edu (News Owner)
  8. Organization: University of Waterloo
  9. References: <1992Jul23.204321.4615@math.waterloo.edu> <1992Jul24.155959.26446@cs.rochester.edu>
  10. Date: Fri, 24 Jul 1992 18:28:55 GMT
  11. Lines: 27
  12.  
  13. In article <1992Jul24.155959.26446@cs.rochester.edu>, fulk@cs.rochester.edu (Mark Fulk) writes:
  14. > In article <1992Jul23.204321.4615@math.waterloo.edu> alopez-o@neumann.waterloo.edu (Alex Lopez-Ortiz) writes:
  15. > >I recall reading about a proof that there exists a problem of complexity 
  16. > >n^2 for which only an exponential lower bound could ever be proven 
  17. > >within some formal system. Iread the note in a survey.
  18. > 
  19. > You clearly have this wrong, since an n^2 problem could not have an
  20. > exponential lower bound.
  21.  
  22. Yes, it is a typo, I meant to write upper bound.
  23.  
  24. >  I suspect that you are referring to work
  25. > of Case and Royer, which shows the existence, for any reasonable formal
  26. > system F, of a problem that is in linear time, provable in F to be in
  27. > quadratic time (a clocked TM is supplied), but not provable in F to be
  28. > in linear time.  The proof is a fairly straightforward diagonalization.
  29. > For details and references, you might email royer@top.cis.syr.edu
  30. > 
  31. > Mark
  32. > -- 
  33. > Mark A. Fulk            University of Rochester
  34. > Computer Science Department    fulk@cs.rochester.edu
  35.  
  36. -- 
  37. Alex Lopez-Ortiz                              alopez-o@maytag.UWaterloo.ca
  38. Deparment of Computer Science                       University of Waterloo
  39. Waterloo, Ontario                                                   Canada
  40.