home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2445 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  2.7 KB
  1. Xref: sparky comp.theory:2445 sci.math:15104 sci.crypt:4908
  2. Newsgroups: comp.theory,sci.math,sci.crypt
  3. Path: sparky!uunet!charon.amdahl.com!pacbell.com!ames!agate!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  4. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <1992Nov17.043640.5525@CSD-NewsHost.Stanford.EDU>
  7. Sender: news@CSD-NewsHost.Stanford.EDU
  8. Organization: Computer Science Department,  Stanford University.
  9. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <15115@ember.UUCP> <Nov.16.16.59.47.1992.6436@remus.rutgers.edu>
  10. Date: Tue, 17 Nov 1992 04:36:40 GMT
  11. Lines: 36
  12.  
  13. In article <Nov.16.16.59.47.1992.6436@remus.rutgers.edu> clong@remus.rutgers.edu (Chris Long) writes:
  14. >Sure, but P=NP and P<>NP are certainly not equally likely.  The a priori
  15. >evidence that P<>NP is *overwhelming*; to claim that P=NP has a chance
  16. >of being true is worse than claiming that there is a chance of only a
  17. >finite number of twin primes existing.  Both are unproven, but there are
  18. >*very* strong reasons for believing them to be true.  So strong that
  19. >anyone who believes otherwise must be either ignorant or a crackpot.
  20.  
  21. If one perturbs the definition of primality slightly while retaining
  22. its basic statistical characteristics (mean, variance) then one can
  23. actually prove such theorems as "There are infinitely many twin primes"
  24. and "Every even number > 3 is the sum of two primes" (Goldbach's
  25. conjecture) without much difficulty.  (I believe "lucky" numbers
  26. provide an instance of this general principle.)  In these proofs the
  27. statistical evidence is overwhelming, encouraging one to assign
  28. extraordinary odds to the failure of Goldbach's conjecture.
  29.  
  30. (I will with no misgivings bet you ten thousand dollars at a thousand
  31. to one odds that no counterexample to Goldbach's conjecture will appear
  32. in the next ten years.  If one is found I owe you ten thousand dollars,
  33. otherwise you owe me ten dollars.  Anyone who's played for a while with
  34. Goldbach's conjecture will see that this is very easy money for me.)
  35.  
  36. There is *no* comparable statistical evidence for either P=NP or
  37. P!=NP.  The evidence to date for P!=NP is that a lot of people have
  38. looked for a fast algorithm for the generic NP problem and failed.  If
  39. you ask me what evidence there is to date for P=NP I will reply that an
  40. even larger set of people have looked for a proof of P!=NP and failed.
  41. If we judge these arguments only by the extent of the search in each
  42. case, an otherwise disinterested bettor would say that the a priori
  43. evidence that P=NP is *overwhelming*.
  44.  
  45. Moshe Vardi has made P=NP his odds-on favorite, I admit I'm a
  46. conservative old coward in sticking to even odds.
  47. -- 
  48. Vaughan Pratt              A fallacy is worth a thousand steps.
  49.