Random Oracle Hypothesis

The (refuted) conjecture, attributed to Bennett and Gill, that complexity-class relationships holding for almost all relativized worlds also hold unrelativized.

Refutation

For almost all oracles $A$, ${\mathbf{IP}}^A\ne {\mathbf{PSPACE}}^A$; in fact ${\mathbf{coNP}}^A⊈{\mathbf{IP}}^A$ — CCG+94. Since IP $=$ PSPACE — Sha90 — the Random Oracle Hypothesis is false. The results extend to multi-prover proof systems, while the variant class $\mathbf{IPP}$ satisfies ${\mathbf{IPP}}^A={\mathbf{PSPACE}}^A$ for every oracle $A$ — CCG+94.