HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Relativization results in class separation

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
resultsclassrelativizationseparation

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#41501, answer score: 7

Revisions (0)

No revisions yet.