The Random Oracle Hypothesis is False


Abstract:

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. This paper shows that the Random Oracle Hypothesis is false by showing that for almost all oracles A, IP(A) is not equal to PSPACE(A). If the Random Oracle Hypothesis were true, it would contradict Shamir's result that IP = PSPACE. In fact, it is shown that for almost all oracles A, coNP(A) is not a subset of IP(A). These results extend to the multi-prover proof systems of Ben-Or, Goldwasser, Kilian and Wigderson. In addition, this paper shows that the Random Oracle Hypothesis is sensitive to small changes in the definition. A class IPP, which is similar to IP, is defined. Surprisingly, the IPP = PSPACE result holds for all oracle worlds.

Last Modified: 22 Jul 2024 11:27:55 EDT by Richard Chang