We know that $P\neq NP$ problem cannot be demonstrated by relativization because there exists oracle relative to which they are equal.

Is there natural complexity classes that has been shown to be equal but are separate under some oracle?

  • $\begingroup$ csee.umbc.edu/~chang/papers/roh/roh.pdf $\;$ $\endgroup$
    – user12859
    Apr 18, 2015 at 2:50
  • $\begingroup$ @RickyDemer This is very weird though. Things that are equal can be separated by oracles. $\endgroup$
    – Turbo
    Apr 18, 2015 at 4:04
  • $\begingroup$ yes relativization is quite a tricky concept. see eg survey role of relativization in complexity theory by fortnow. there are also some cutting edge new results by Rossman et al on PH. $\endgroup$
    – vzn
    Apr 20, 2015 at 0:52
  • $\begingroup$ see also validity of oracles in math arguments $\endgroup$
    – vzn
    Apr 20, 2015 at 1:00
  • $\begingroup$ @Turbo There is equal, and there is equal. When we write IP=PSPACE, we mean that the set of problems in PSPACE is equal to the set of problems in IP. But IP is not equal to PSPACE in terms of how they are defined. $\endgroup$
    – Pål GD
    Apr 20, 2015 at 7:34

1 Answer 1


Yes, check out the classes IP (interactive polynomial time) and PSPACE (polynomial space).

In 1988, Fortnow and Sipser [1] showed that these two classes have contradictory relativizations, that is, there exist oracles $A$ and $B$ ($A$ can be chosen to be $\text{PSPACE}$ itself) such that $$\text{IP}^A = \text{PSPACE}^A\text{, and}$$ $$\text{IP}^B \neq \text{PSPACE}^B .$$

Later, Shamir [2] showed that $\text{IP} = \text{PSPACE}$.

Chang et al. furthermore showed that for a random oracle $A$, $\text{IP}^A \neq \text{PSPACE}^A$ [3]. See ibid. for a nice introduction and overview. This result actually disproves the Random Oracle Hypothesis which states that

the relationships between complexity classes which hold for almost all oracles must also hold in the unrelativized case [3].


[1] Fortnow, L. & Sipser, M., Are there interactive protocols for co-NP languages?, Inform. Process. Lett. 28, No. 5 (1988), 249-251.

[2] Shamir, A. IP = PSPACE, in "Proceedings, IEEE Symposium on Foundations of Computer Science, 1990," pp. 11-15.

[3] Chang, R., Chor, B., Goldreich, O., Hartmanis, J., Håstad, J., Ranjan, D., & Rohatgi, P. (1994). The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1), 24-39.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.