Back to Computational Complexity
Back to notes

# MIP = NEXP

30%

In this note, we are going to prove that $\MIP=\NEXP$. Before we prove the main theorem, let’s first recall several useful facts about multi-prover interactive proof system.

## Multi-prover interactive proof and probabilistic oracle Turing machine

In the early 90s, Fortnow, Rompel, and Sipser showed the equivalence of multi-prover interactive proof and probabilistic oracle Turing machines.

A language $L$ is accepted by a probabilistic oracle TM iff $L$ is accepted by a multi-prover interactive proof systems.

Please refer to this note for details.

A language $L$ is accepted by a probabilistic oracle TM in polynomial time iff $L\in\MIP$.

• All language in $\NP$ has perfect zero-knowledge two-prover proof system while one-prover is true unless polynomial hierarchy collapses.
• If a language $L$ is accepted by a multi-prover interactive proof system, then $L$ is accepted by a two-prover interactive proof system.

## MIP = NEXP

In 1991, Babai, Fortnow, and Lund proved that $\MIP=\NEXP$. Namely, by our belief of $\P\neq\NP$, $\MIP$ is strictly more powerful than $\IP$.

$\NEXP=\MIP$.

• ($\MIP\subseteq\NEXP$) First, since $\MIP$ is equivalent to PPT OTM, we consider PPT OTM instead. Now, we can non-deterministically guess an oracle $O$ and enumerate all randomness. Count how many randomness successes. Thus, by the completeness and soundness guaranteed, we can distinguish if we guess right/wrong.
• ($\NEXP\subseteq\MIP$) A very roughly proof idea is sketched as follows.
1. Arithmetize $\NEXP$: Let $L\in\NEXP$. For any $x\in{0,1}^n$, there’s a polynomial $P_x$ such that $x\in L$ iff $P_x$ has a root. Moreover, $P_x$ is computable in $poly(n)$ time.
2. Design PPT OTM first guessing the root of $P_x$. By Schwartz-Zippel lemma, we can proved this works.