home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 5161 < prev    next >
Encoding:
Internet Message Format  |  1992-11-21  |  2.7 KB
  1. Xref: sparky sci.crypt:5161 comp.theory:2503 sci.math:15352
  2. Path: sparky!uunet!cs.utexas.edu!uwm.edu!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,comp.theory,sci.math
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <1emgqgINNacb@iskut.ucs.ubc.ca>
  7. Date: 21 Nov 92 23:30:24 GMT
  8. References: <BxzD1t.3xA.2@cs.cmu.edu> <722273103@pike.cs.duke.edu> <By2tv0.BDn.2@cs.cmu.edu>
  9. Distribution: inet
  10. Organization: University of British Columbia, Vancouver, B.C., Canada
  11. Lines: 43
  12. NNTP-Posting-Host: gauss.math.ubc.ca
  13.  
  14. In article <By2tv0.BDn.2@cs.cmu.edu> sgall+@CS.CMU.EDU (Jiri Sgall) writes:
  15. >1. I have an explicit algorithm for factoring which is polynomial if P=NP. 
  16. >(No matter if you prove that nonconstructively.)
  17.  
  18. This is correct: it depends upon the factorization problem being in NP
  19. and co-NP. On input n, the algorithm applies assorted other algorithms
  20. to the number n, in parallel, occasionally adding new ones to the
  21. "pool", and scans the output for a factorization of n, together with a
  22. proof that the factors are prime. There *always* exists a short such
  23. factorization *and* short proof that it is correct. The only problem
  24. is with finding it.
  25.  
  26. If P=NP, then one of the algorithms out there is a "smart" one which
  27. solves the problem in time polynomial in the length of n (log n). One
  28. will eventually add it to the pool. Of course, you won't know which
  29. one it is, but it will give you the factorization with proof. This
  30. algorithm is hopelessly slow, however, as the constant in the time
  31. required for it to run depends upon the number of algorithms one would
  32. have to search through, one by one, before encountering the magic
  33. algorithm which factorizes quickly.
  34.  
  35. >2. I have an explicit algorithm that finds a satisfying assignement of a 
  36. >satisfiable formula (but may run forever on an unsatisfiable one) if P=NP.
  37.  
  38. This is also true, and if P=NP the algorithm can be made to find the
  39. satisfying assignment in polynomial time. Note that this is not the
  40. same as having an algorithm which solves the satisfiability problem,
  41. since you don't know how long you might have to wait for the program
  42. to find the assignment.
  43.  
  44. *If* you knew what the polynomial was, which bounded the length of
  45. time required to find the assignment, then you *would* be able to make
  46. it into a genuine algorithm for solving the satifiability problem, by
  47. making it stop with a negative result once the time limit has been
  48. passed.
  49.  
  50. Not having a limit on the size of the algorithm required, and on the
  51. polynomial bounding the length of time it would require to operate, is
  52. the essential reason why one might (so far as we can tell) have a
  53. non-constructive proof of P=NP.
  54.  
  55. Keith Ramsay
  56. ramsay@unixg.ubc.ca
  57.