home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2508 < prev    next >
Encoding:
Text File  |  1992-11-22  |  2.5 KB  |  54 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  3. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  4. Subject: Re: Cryptography and P=NP
  5. Message-ID: <1992Nov23.033725.22456@CSD-NewsHost.Stanford.EDU>
  6. Sender: news@CSD-NewsHost.Stanford.EDU
  7. Organization: Computer Science Department,  Stanford University.
  8. References: <1992Nov17.043640.5525@CSD-NewsHost.Stanford.EDU> <1992Nov22.171847.27106@athena.mit.edu> <102829@bu.edu>
  9. Date: Mon, 23 Nov 1992 03:37:25 GMT
  10. Lines: 42
  11.  
  12. In article <1992Nov22.171847.27106@athena.mit.edu> patl@athena.mit.edu (Patrick J. LoPresti) writes:
  13. >
  14. >Isn't it true that, with respect to a random oracle, P!=NP with
  15. >probability 1?
  16.  
  17. The same argument with "set of Gods" in place of "oracle" proves the
  18. existence of a God.  There are infinitely many possible sets of Gods,
  19. only one of which is the empty set.  Hence with probability 1 there is
  20. a God.
  21.  
  22. See you in church.  :-)
  23.  
  24.  
  25. With regard to the analogy with Goldbach's conjecture, I believe the
  26. number of representations of 2n by a sum of two primes is close to that
  27. expected statistically, certainly for as far out as this test has been
  28. conducted (anyone have concrete figures on this?).  Since this hit rate
  29. grows at something like n/log^2 n, the probability of getting 0 hits
  30. for some value of 2n instead of the expected n/log^2 n hits, out beyond
  31. where the conjecture is currently known to hold, can be calculated
  32. quite explicitly to be a certain *very* miniscule yet definitely nonzero
  33. number.
  34.  
  35. The corresponding statistics for random oracles are rendered
  36. meaningless by the arbitrariness of the measure chosen for their
  37. distribution.  For Goldbach there is no arbitrariness in the measure,
  38. the set of primes below 2n consists of around 2n/log n primes with a
  39. quite well (though not perfectly) understood distribution.
  40.  
  41.  
  42. In article <102829@bu.edu> gene@cs.bu.edu (Gene Itkis) writes:
  43. >There has been a number of fairly recent results contradicting the random
  44. >oracle conjecture. Basically, these results indicate that the "statistical
  45. >evidence" from the random oracle is not very reliable. The results include
  46. >IP=PSPACE, MIP=NEXPTIME and others (these theorems are false with respect to
  47. >random oracle with prob 1, but true in the absence of oracles).
  48.  
  49. I overheard at FOCS that Juris Hartmanis has recently been marshalling
  50. further arguments of this type against the significance of
  51. relativization results to P=NP, which I'm looking forward to seeing.
  52. -- 
  53. Vaughan Pratt              A fallacy is worth a thousand steps.
  54.