home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 4851 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  1.8 KB
  1. Xref: sparky sci.crypt:4851 sci.math:15029 comp.theory:2432
  2. Newsgroups: sci.crypt,sci.math,comp.theory
  3. Path: sparky!uunet!telebit!phr
  4. From: phr@telebit.com (Paul Rubin)
  5. Subject: Re: Cryptography and P=NP
  6. In-Reply-To: ramsay@math.ubc.ca's message of 16 Nov 1992 06:43:57 GMT
  7. Message-ID: <PHR.92Nov16003614@napa.telebit.com>
  8. Sender: news@telebit.com
  9. Nntp-Posting-Host: napa.telebit.com
  10. Organization: Telebit Corporation; Sunnyvale, CA, USA
  11. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu>
  12.     <PHR.92Nov15203840@napa.telebit.com> <1e7fvdINN87s@iskut.ucs.ubc.ca>
  13. Distribution: inet
  14. Date: 16 Nov 92 00:36:14
  15. Lines: 18
  16.  
  17.     Mathematics would also be placed in a surprising position by P=NP.
  18.     P=NP implies that there is an algorithm which, given a theorem
  19.     expressed formally in ZF, say, and a number n, either gives a formal
  20.     proof of the theorem of length at most n, or shows that there is none,
  21.     and which would take time bounded by some polynomial in n. It wouldn't
  22.     *necessarily* put us all out of the math research business, but....
  23.  
  24. I don't know that this is really so interesting: the kinds of things
  25. we write down in mathematical proofs ("by symmetry, X, and by
  26. induction on n, Z") often would have very large expansions in formal
  27. proofs.  The kind of thing a mathematician would write down as a proof
  28. of a theorem is less like shorthand for a formal proof than like a
  29. computer program which generates a formal proof.  So we're not so
  30. interested in the length of the formal proof as in the length of the
  31. shortest such program.  But recognizing whether a program P generates
  32. a proof of a theorem T is not in NP---it's not even undecidable
  33. (because we can't even tell if P ever halts).  Thus, my feeling is
  34. that even an NP-oracle wouldn't put mathemeticians out of business.
  35.