<p>I found some other articles: </p>

<p>Theorem 5.1 in <a href="http://www.sciencedirect.com.proxy.uba.uva.nl:2048/science/article/pii/0304397594902518" rel="nofollow noreferrer">this article</a> gives an oracle $A$ s.t. $\mathsf{coNP}^A \not\subseteq \mathsf{MIP}^A$.</p>

<p>You also have theorem 5.2 in <a href="https://pdfs.semanticscholar.org/70d7/33a1dd5bd36c09b24c07e37e73d92834cd85.pdf" rel="nofollow noreferrer">this article</a>, concerning $\mathsf{NP}$ and $\mathsf{PCP}$</p>

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

<p>There are also some counterexamples to the random oracle hypthesis, which is related:
<a href="http://www.sciencedirect.com/science/article/pii/S0019995883800230" rel="nofollow noreferrer">Kurz</a>,
<a href="http://nwwwn.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1990/CS/CS0631.pdf" rel="nofollow noreferrer">Chor, Goldreich, Hastad</a>
or <a href="http://www.sciencedirect.com/science/article/pii/S0022000005800844" rel="nofollow noreferrer">Chang et al</a></p>

CC BY-SA 3.0
2017-08-30T19:41:13.423Z
2017-08-30T19:50:52.620Z
2017-08-30T19:50:52.620Z
Mal
<p>$\mathsf{MA_{EXP}} \not\subseteq \mathsf{P/poly}$ but there is an oracle relative to which this is false; both were proved in </p>

<blockquote>
  <p>H. Buhrman, L. Fortnow, T. Thierauf. <a href="http://doi.org/10.1109/CCC.1998.694585" rel="nofollow noreferrer">Nonrelativizing separations</a>. CCC '98. (<a href="http://bibbase.org/network/publication/buhrman-fortnow-thierauf-nonrelativizingseparations-1998" rel="nofollow noreferrer">freely available author's version</a>)</p>
</blockquote>

CC BY-SA 3.0
2017-08-30T16:05:47.567Z
2017-08-30T17:19:59.737Z
2017-08-30T17:19:59.737Z
Joshua Grochow
<p>In <a href="http://www.sciencedirect.com/science/article/pii/S0022000005800844" rel="noreferrer">this article</a> Chang et al. provide a counterexample by giving an oracle $A$ such that $\mathsf{IP}^A \neq \mathsf{PSPACE}^A$. </p>

<p>I wanted to know if there are more examples like this.</p>

CC BY-SA 3.0
2017-08-29T15:55:11.443Z
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](https://cstheory.stackexchange.com/q/2045/129),
 [this](https://cstheory.stackexchange.com/q/37332/129), [this](https://cstheory.stackexchange.com/q/6575/129), or [this](https://cstheory.stackexchange.com/q/21200/129).
Joshua Grochow
CC BY-SA 3.0
2017-08-30T15:04:17.277Z
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.
Mal
<complexity-classes><oracles><relativization><random-oracles>
What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?
Mal
# What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

(Asked by: username_0 on 2017-08-29)

In [this article](http://www.sciencedirect.com/science/article/pii/S0022000005800844) 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.

**Tags:** complexity-classes, oracles, relativization, random-oracles

> **Comments:**
> **username_1**: 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](https://cstheory.stackexchange.com/q/2045/129),  [this](https://cstheory.stackexchange.com/q/37332/129), [this](https://cstheory.stackexchange.com/q/6575/129), or [this](https://cstheory.stackexchange.com/q/21200/129).  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_1 on 2017-08-30. Score: 7 | Accepted answer

$\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](http://doi.org/10.1109/CCC.1998.694585). CCC '98. ([freely available author's version](http://bibbase.org/network/publication/buhrman-fortnow-thierauf-nonrelativizingseparations-1998))


---

### Answer by username_0 on 2017-08-30. Score: 0

I found some other articles:

Theorem 5.1 in [this article](http://www.sciencedirect.com.proxy.uba.uva.nl:2048/science/article/pii/0304397594902518) gives an oracle $A$ s.t. $\mathsf{coNP}^A \not\subseteq \mathsf{MIP}^A$.

You also have theorem 5.2 in [this article](https://pdfs.semanticscholar.org/70d7/33a1dd5bd36c09b24c07e37e73d92834cd85.pdf), 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](http://www.sciencedirect.com/science/article/pii/S0019995883800230),
[Chor, Goldreich, Hastad](http://nwwwn.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1990/CS/CS0631.pdf)
or [Chang et al](http://www.sciencedirect.com/science/article/pii/S0022000005800844)


---

