home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 5162 < prev    next >
Encoding:
Internet Message Format  |  1992-11-21  |  1.6 KB
  1. Xref: sparky sci.crypt:5162 sci.math:15353 comp.theory:2504
  2. Path: sparky!uunet!cs.utexas.edu!usc!rutgers!micro-heart-of-gold.mit.edu!uw-beaver!cs.ubc.ca!unixg.ubc.ca!ramsay
  3. From: ramsay@math.ubc.ca (Keith Ramsay)
  4. Newsgroups: sci.crypt,sci.math,comp.theory
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <1emhb6INNadc@iskut.ucs.ubc.ca>
  7. Date: 21 Nov 92 23:39:18 GMT
  8. References: <1992Nov19.172719.1540@fid.morgan.com> <1992Nov19.193036.26711@rchland.ibm.com> <1992Nov21.191944.87493@Cookie.secapl.com>
  9. Distribution: inet
  10. Organization: University of British Columbia, Vancouver, B.C., Canada
  11. Lines: 20
  12. NNTP-Posting-Host: gauss.math.ubc.ca
  13.  
  14. In article <1992Nov21.191944.87493@Cookie.secapl.com>
  15. frank@Cookie.secapl.com (Frank Adams) writes:
  16.  
  17. >Given a problem which actually is in NP, this universal machine will in fact
  18. >solve it in polynomial time if P=NP -- indeed, it will solve any problem in
  19. >P, given an NP formulation, in polynomial time.  If the NP problem is in not
  20. >in P, it will always halt, but will not necessarily run in polynomial time.
  21.  
  22. There is a problem with what you say here. Suppose we have a problem
  23. formulated as an NP problem, but which is in fact in P. This
  24. "universal" algorithm will indeed halt in polynomial time for the
  25. cases for which the answer is "yes" (by finding the "non-deterministic
  26. guess" required to show that the answer is indeed "yes"). If the
  27. answer to the problem is "no", however, one may not know when to stop
  28. looking for a positive answer. For it really to solve such a
  29. problem-class in polynomial time, it has to have some rule for
  30. determining when to say "no".
  31.  
  32. Keith Ramsay
  33. ramsay@unixg.ubc.ca
  34.