6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ csee.umbc.edu/~chang/papers/roh/roh.pdf $\;$ $\endgroup$ – user12859 Apr 18 '15 at 2:50
  • $\begingroup$ @RickyDemer This is very weird though. Things that are equal can be separated by oracles. $\endgroup$ – T.... Apr 18 '15 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 '15 at 0:52
  • $\begingroup$ see also validity of oracles in math arguments $\endgroup$ – vzn Apr 20 '15 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 '15 at 7:34
5
$\begingroup$

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].

References

[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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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