home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2505 < prev    next >
Encoding:
Internet Message Format  |  1992-11-22  |  1.8 KB
  1. Xref: sparky comp.theory:2505 sci.math:15366 sci.crypt:5183
  2. Newsgroups: comp.theory,sci.math,sci.crypt
  3. Path: sparky!uunet!europa.asd.contel.com!darwin.sura.net!zaphod.mps.ohio-state.edu!rpi!think.com!snorkelwacker.mit.edu!bloom-picayune.mit.edu!athena.mit.edu!patl
  4. From: patl@athena.mit.edu (Patrick J. LoPresti)
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <1992Nov22.171847.27106@athena.mit.edu>
  7. Sender: news@athena.mit.edu (News system)
  8. Nntp-Posting-Host: marinara.mit.edu
  9. Organization: Massachusetts Institute of Technology
  10. References: <15115@ember.UUCP> <Nov.16.16.59.47.1992.6436@remus.rutgers.edu> <1992Nov17.043640.5525@CSD-NewsHost.Stanford.EDU>
  11. Date: Sun, 22 Nov 1992 17:18:47 GMT
  12. Lines: 29
  13.  
  14. (My apologies if this shows up twice.  An earlier reply never appeared
  15. at my site.)
  16.  
  17. In article <1992Nov17.043640.5525@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
  18. >
  19. >If one perturbs the definition of primality slightly while retaining
  20. >its basic statistical characteristics (mean, variance) then one can
  21. >actually prove such theorems as "There are infinitely many twin primes"
  22. >and "Every even number > 3 is the sum of two primes" (Goldbach's
  23. >conjecture) without much difficulty.  (I believe "lucky" numbers
  24. >provide an instance of this general principle.)  In these proofs the
  25. >statistical evidence is overwhelming, encouraging one to assign
  26. >extraordinary odds to the failure of Goldbach's conjecture.
  27. >
  28. [stuff deleted]
  29. >
  30. >There is *no* comparable statistical evidence for either P=NP or
  31. >P!=NP.  The evidence to date for P!=NP is that a lot of people have
  32. >looked for a fast algorithm for the generic NP problem and failed.
  33. [more stuff deleted]
  34.  
  35.  
  36. Isn't it true that, with respect to a random oracle, P!=NP with
  37. probability 1?
  38.  
  39. How does this "statistical" evidence differ from your example
  40. regarding the Goldbach conjecture?
  41.  
  42. - Pat
  43.