Content deleted Content added
MOS:HEAD |
→Random oracle hypothesis: Section is unclear and hard to read Tags: Mobile edit Mobile web edit Advanced mobile edit |
||
Line 33:
== Random oracle hypothesis ==
{{section rewrite}}
Although the Baker–Gill–Solovay theorem<ref name="BGS75">{{cite journal| first1 = Theodore | last1 = Baker | first2 = John | last2 = Gill | first3 = Robert | last3 = Solovay | title = Relativizations of the P =? NP Question | year = 1975 | journal = SIAM J. Comput. |volume=4|issue=4| publisher = SIAM | pages = 431–442 | doi = 10.1137/0204037 }}</ref> showed that there exists an oracle A such that P<sup>A</sup> = NP<sup>A</sup>, subsequent work by Bennett and Gill,<ref name="BG81">{{cite journal| title = Relative to a Random Oracle A, P != NP != co-NP with Probability 1 | first1 = Charles | last1 = Bennett | first2 = John | last2 = Gill | year = 1981 | publisher = SIAM | journal = SIAM J. Comput.|volume=10|issue=1 | pages = 96–113| doi = 10.1137/0210008 }}</ref> showed that for a ''random oracle'' B (a function from {0,1}<sup>n</sup> to {0,1} such that each input element maps to each of 0 or 1 with probability 1/2, independently of the mapping of all other inputs), P<sup>B</sup> ⊊ NP<sup>B</sup> with probability 1. Similar separations, as well as the fact that random oracles separate classes with probability 0 or 1 (as a consequence of the [[Kolmogorov's zero–one law]]), led to the creation of the '''Random Oracle Hypothesis''', that two "acceptable" complexity classes C<sub>1</sub> and C<sub>2</sub> are equal if and only if they are equal (with probability 1) under a random oracle (the acceptability of a complexity class is defined in BG81<ref name="BG81" />). This hypothesis was later shown to be false, as the two acceptable complexity classes [[IP (complexity)|IP]] and [[PSPACE]] were shown to be equal<ref>{{cite journal|first=Adi|last=Shamir|title= IP = PSPACE|journal=Journal of the ACM|volume=39|issue=4|pages=869–877|date=October 1992|doi=10.1145/146585.146609|s2cid=315182|doi-access=free}}</ref> despite IP<sup>A</sup> ⊊ PSPACE<sup>A</sup> for a random oracle A with probability 1.<ref name="CCGHHRR">{{cite journal|first1=Richard|last1= Chang|first2= Benny|last2= Chor|author2-link= Benny Chor |first3= Oded |last3=Goldreich|first4= Juris|last4= Hartmanis|first5= Johan|last5= Hastad|first6= Desh|last6= Ranjan|first7= Pankaj|last7= Rohatgi|title= The Random Oracle Hypothesis is False|journal=Journal of Computer and System Sciences|volume= 49|issue=1|pages=24–39|date=August 1994|doi= 10.1016/S0022-0000(05)80084-4|issn=0022-0000|url= http://citeseer.ist.psu.edu/282397.html|doi-access= free}}</ref>
| |||