home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 4987 < prev    next >
Encoding:
Internet Message Format  |  1992-11-18  |  1.7 KB
  1. Xref: sparky sci.crypt:4987 sci.math:15202 comp.theory:2463
  2. Newsgroups: sci.crypt,sci.math,comp.theory
  3. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!malgudi.oar.net!news.ans.net!newsgate.watson.ibm.com!yktnews!admin!wo0z!lwloen
  4. From: lwloen@rchland.vnet.ibm.com (Larry Loen)
  5. Subject: Re: Cryptography and P=NP
  6. Sender: news@rchland.ibm.com
  7. Message-ID: <1992Nov18.193900.20199@rchland.ibm.com>
  8. Date: Wed, 18 Nov 1992 19:39:00 GMT
  9. Distribution: inet
  10. Reply-To: lwloen@vnet.ibm.com
  11. Disclaimer: This posting represents the poster's views, not necessarily those of IBM
  12. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <PHR.92Nov15203840@napa.telebit.com> <1e7fvdINN87s@iskut.ucs.ubc.ca> <1992Nov16.084503.10141@vax.oxford.ac.uk> <BxvEF3.Kqw.2@cs.cmu.edu>
  13. Nntp-Posting-Host: wo0z.rchland.ibm.com
  14. Organization: IBM Rochester
  15. Lines: 21
  16.  
  17. In article <BxvEF3.Kqw.2@cs.cmu.edu> Jiri Sgall writes:
  18.  
  19. >(partial quote of James Annan):
  20.  
  21. >|> And remember, proving P=NP doesn't necessarily mean finding such an algorithm,
  22. >|> merely proving it exists.
  23. >|> 
  24.  
  25. >Once you have the proof, you can easily run a kind of universal algorithm,
  26. >which will be guaranteed to be polynomial
  27.  
  28. OK, I don't know beans about P and NP.  So, an elementary question:
  29.  
  30. Do all programs of class P halt?  Your "universal algorithm" seems perilously
  31. close to the "halting" problem and I have never been able to eliminate it
  32. from far simpler cases than P or NP.  Or, is the halting issue kind of a
  33. separate point/issue (ie, the solution is "P" when it works)?
  34.  
  35. -- 
  36.    Larry W. Loen        |  My Opinions are decidedly my own, so please
  37.                         |  do not attribute them to my employer
  38.