home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 4899 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  1.7 KB
  1. Xref: sparky sci.crypt:4899 sci.math:15095 comp.theory:2444
  2. Path: sparky!uunet!wupost!cs.utexas.edu!uwm.edu!zaphod.mps.ohio-state.edu!caen!spool.mu.edu!agate!doc.ic.ac.uk!uknet!comlab.ox.ac.uk!oxuniv!annan
  3. From: annan@vax.oxford.ac.uk
  4. Newsgroups: sci.crypt,sci.math,comp.theory
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <1992Nov16.084503.10141@vax.oxford.ac.uk>
  7. Date: 16 Nov 92 08:45:03 GMT
  8. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <PHR.92Nov15203840@napa.telebit.com> <1e7fvdINN87s@iskut.ucs.ubc.ca>
  9. Distribution: inet
  10. Organization: Oxford University VAX 6620
  11. Lines: 23
  12.  
  13. In article <1e7fvdINN87s@iskut.ucs.ubc.ca>, ramsay@math.ubc.ca (Keith Ramsay) writes:
  14. > In article <PHR.92Nov15203840@napa.telebit.com> phr@telebit.com 
  15. > (Paul Rubin) writes:
  16. >>It is true that if P=NP then all cryptography everywhere (not just RSA)
  17. >>is dead; but at this point I wouldn't take Swart's claims seriously
  18. >>without seeing some consensus among complexity efforts that unlike
  19. >>his previous attempts, his latest effort is free of bugs.
  20. > 
  21. > Mathematics would also be placed in a surprising position by P=NP.
  22. > P=NP implies that there is an algorithm which, given a theorem
  23. > expressed formally in ZF, say, and a number n, either gives a formal
  24. > proof of the theorem of length at most n, or shows that there is none,
  25. > and which would take time bounded by some polynomial in n. It wouldn't
  26. > *necessarily* put us all out of the math research business, but....
  27.  
  28. And remember, proving P=NP doesn't necessarily mean finding such an algorithm,
  29. merely proving it exists.
  30.  
  31. -- 
  32. James Annan.
  33.                 [--------------------------------------]
  34.                 [  "The only good Tory is a lavatory"  ]
  35.                 [--------------------------------------]
  36.