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
-
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$– Joshua GrochowCommented 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$– MalCommented Aug 30, 2017 at 15:04
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
$\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)
answered Aug 30, 2017 at 16:05
$\begingroup$
$\endgroup$
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