In this article Chang et al. provide a counterexample by giving an oracle $A$ such that $\mathsf{IP}^A \neq \mathsf{PSPACE}^A$.

I wanted to know if there are more examples like this.

  • 2
    $\begingroup$ If you just want an oracle where $\mathsf{IP} \neq \mathsf{PSPACE}$, it goes back to Fortnow-Sipser '88, who gave an oracle relative to which $\mathsf{IP}$ didn't even contain $\mathsf{coNP}$. Your question is essentially the same as asking for non-relativizing techniques that have been used to resolve complexity class (in)equalities; see, e.g., this, this, this, or this. $\endgroup$ Aug 29, 2017 at 15:55
  • $\begingroup$ Thank you! The Fortnow-Sipser article is very helpful. And you are right, the questions are similar but I wouldn't say they are equal. For example, I have not been able to find an oracle relative to which $\mathsf{MIP}$ and $\mathsf{NEXP}$ are unequal, and it is these sort of oracle results that I am interested in. $\endgroup$
    – Mal
    Aug 30, 2017 at 15:04

2 Answers 2


$\mathsf{MA_{EXP}} \not\subseteq \mathsf{P/poly}$ but there is an oracle relative to which this is false; both were proved in

H. Buhrman, L. Fortnow, T. Thierauf. Nonrelativizing separations. CCC '98. (freely available author's version)


I found some other articles:

Theorem 5.1 in this article gives an oracle $A$ s.t. $\mathsf{coNP}^A \not\subseteq \mathsf{MIP}^A$.

You also have theorem 5.2 in this article, concerning $\mathsf{NP}$ and $\mathsf{PCP}$

Apparently Hartmanis wrote an article called "solvable problems with conflicting relativizations" but I cannot find this online (help?).

There are also some counterexamples to the random oracle hypthesis, which is related: Kurz, Chor, Goldreich, Hastad or Chang et al


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.