home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 5027 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  1.9 KB
  1. Path: sparky!uunet!elroy.jpl.nasa.gov!sdd.hp.com!swrinde!emory!gatech!rutgers!igor.rutgers.edu!zodiac.rutgers.edu!leichter
  2. From: leichter@zodiac.rutgers.edu
  3. Newsgroups: sci.crypt
  4. Subject: Re: Cryptography and P=NP
  5. Message-ID: <1992Nov19.142510.1@zodiac.rutgers.edu>
  6. Date: 19 Nov 92 19:25:10 GMT
  7. 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> <1992Nov18.193900.20199@rchland.ibm.com> <1992Nov19.102822.1@zodiac.rutger
  8. Sender: news@igor.rutgers.edu
  9. Followup-To: sci.crypt
  10. Distribution: inet
  11. Organization: Rutgers University Department of Computer Science
  12. Lines: 20
  13. Nntp-Posting-Host: cancer.rutgers.edu
  14.  
  15. In article <1992Nov19.102822.1@zodiac.rutgers.edu>, I said:
  16. | Yes.  Programs in class P are defined as those for which, for any input of
  17. | length n, we can prove they halt after taking no more than p(n) steps, where
  18. | p is some polynomial.
  19.  
  20. This is poorly stated.  Whether a program is in P or not is a fact, whether we
  21. can prove if or not.  A program is in P if there exists a polynomial p such
  22. that, for any input of length n, the program will, in fact, halt in most p(n)
  23. steps.  If proving that things were or were not in P were trivial, then the
  24. question of whether P equals NP would be trivial, too:  Because, say, 3-SAT
  25. is complete for NP, if we could prove 3-SAT was in P, we'd know P=NP; if we
  26. could prove 3-SAT was NOT in P, then P!=NP.  As it is, we simply don't know.
  27.  
  28. (And, yes, there are all sorts of philosophical - and mathematical! - com-
  29. plexities to the question of what "actually does halt" means!  Since it is
  30. known that there are oracles relative to which one can prove P=NP, and others
  31. relative to which one can prove P!=NP, in a sense there are "plausible worlds"
  32. (or very slightly more general notions of computation) in which P=NP, and
  33. other "plausible worlds" in which P!=NP.)
  34.                             -- Jerry
  35.