The random oracle hypothesis is false
β
Richard Chang; Benny Chor; Oded Goldreich; Juris Hartmanis; Johan HΓ₯stad; Desh R
π
Article
π
1994
π
Elsevier Science
π
English
β 827 KB
The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the unrelativized case. Although this paper is not the first to provide a counterexample to the Random Ora