home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2506 < prev    next >
Encoding:
Internet Message Format  |  1992-11-22  |  1.2 KB
  1. Xref: sparky comp.theory:2506 sci.math:15370 sci.crypt:5189
  2. Path: sparky!uunet!gatech!rutgers!micro-heart-of-gold.mit.edu!bu.edu!csd!gene
  3. From: gene@cs.bu.edu (Gene Itkis)
  4. Newsgroups: comp.theory,sci.math,sci.crypt
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <102829@bu.edu>
  7. Date: 22 Nov 92 20:07:06 GMT
  8. References: <Nov.16.16.59.47.1992.6436@remus.rutgers.edu> <1992Nov17.043640.5525@CSD-NewsHost.Stanford.EDU> <1992Nov22.171847.27106@athena.mit.edu>
  9. Sender: news@bu.edu
  10. Followup-To: comp.theory
  11. Organization: Computer Science Department, Boston University, Boston, MA, USA
  12. Lines: 14
  13. Originator: gene@csd
  14.  
  15. In article <1992Nov22.171847.27106@athena.mit.edu> patl@athena.mit.edu (Patrick J. LoPresti) writes:
  16. >
  17. >Isn't it true that, with respect to a random oracle, P!=NP with
  18. >probability 1?
  19.  
  20. There has been a number of fairly recent results contradicting the random
  21. oracle conjecture. Basically, these results indicate that the "statistical
  22. evidence" from the random oracle is not very reliable. The results include
  23. IP=PSPACE, MIP=NEXPTIME and others (these theorems are false with respect to
  24. random oracle with prob 1, but true in the absence of oracles).
  25.  
  26. -- 
  27.  ---
  28.     Gene Itkis        (gene@cs.bu.edu)
  29.