<blockquote>
  <p>Can we prove $\mathsf{MIP}=\mathsf{NEXP}$ using the PCP theorem $\mathsf{NP}=\mathsf{PCP(log(n),O(1))}$ as a shortcut?</p>
</blockquote>

<p>$\mathsf{MIP}$ is the class of languages with multi-prover interactive proof systems.</p>

<hr>

<p>Here is what I know:</p>

<p>Intuitively, it's hard for me to see how another prover adds any power to the protocol. The only way I can think of is to somehow make the two provers contradict each other to easily detect false positives. </p>

<p>I have come across the implication that $\mathsf{NEXP}=\mathsf{PCP}(n^{O(1)},O(1))$ and tried to use it, but I fail to understand why the following protocol doesn't work for a single prover: </p>

<ol>
<li><p>ask the prover for the length of the exponential certificate.</p></li>
<li><p>repeat C times: (for some constant C which we know exists due to the above theorem).</p>

<ul>
<li>generate a random index to the certificate and ask the prover to hand over the bits from the given location.</li>
<li>verify that the certificate is still valid, otherwise reject.</li>
</ul></li>
<li><p>after C successful queries - accept.</p></li>
</ol>

<p>Obviously there is some defect in this protocol because $\mathsf{IP}=\mathsf{PSPACE}$ and it has not been proven that $\mathsf{PSPACE}=\mathsf{NEXP}$ (which would be implied if the protocol is correct).</p>

<p>Also the following paper seems relevant:</p>

<ul>
<li>Laszlo Babai, Lance Fortnow and Carsten Lund, "<a href="http://portal.acm.org/citation.cfm?id=1398742" rel="nofollow">Nondeterministic exponential time has two-prover interactive protocols</a>", 1990.</li>
</ul>

<hr>

<h3>Note:</h3>

<p>The question was a homework but was posted more than a year ago.</p>

CC BY-SA 3.0
2011-12-13T00:28:28.550Z
Why do you "need" to write this proof ? is it a homework question ?
Suresh Venkat
CC BY-SA 3.0
2011-12-13T03:46:32.470Z
The way the question is stated sounds as if it is a homework.  But personally I fail to see how the blackbox statement NP=PCP(log,const) implies MIP=NEXP (probably because I am just too dumb).
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-13T12:09:26.813Z
It is certainly true that NP=PCP(log, const) implies that multiple-prover interactive proofs with logarithmic communication is NP. You then have to make everything exponentially bigger to get MIP=NEXP; I don't know how many technical details are involved in this step.
Peter Shor 
CC BY-SA 3.0
2011-12-13T12:58:50.757Z
Making my previous comment more precise, I am pretty sure that no easy proof of a stronger implication NP=PCP(log,const)⇒NEXP=PCP(poly,const) is known (see [Meir 2011](http://eccc.hpi-web.de/report/2011/104/)).  But I will not rule out the possibility that there is an easy way to prove NP=PCP(log,const)⇒MIP=NEXP without proving the stronger implication, although I cannot see how.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-13T14:42:08.863Z
why does this question have three negative votes? Because of the word "need" I am thinking, and the lack of subsequent participation by the asker. Change "need" to "want" and this seems clearly on topic for the site.
Aaron Sterling
CC BY-SA 3.0
2011-12-14T12:05:10.070Z
@Aaron: In fact, there are other deficiencies in the question.  (1) The question contains some ambitious statement as an “assumption” and therefore it is hard to understand what the question really is.  (2) “A 40 page long article proving the required (for the first time, I believe)” is a terrible way to cite a paper.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-14T13:29:31.810Z
@Tsuyoshi: I agree. If the asker had returned to the question, those points hopefully would have been cleaned up.
Aaron Sterling
CC BY-SA 3.0
2011-12-16T15:50:44.950Z
The protocol you give doesn't work because the prover could cheat by reporting different results for the bit at location 2, depending on which location 1 you asked him for. If you have two provers, this can't happen. I find writing down an explicit cheating strategy for the prover to be quite hard for some protocols, but I assume such a strategy must exist.
Peter Shor 
CC BY-SA 3.0
2011-12-16T16:57:48.897Z
PCP[O(log n), O(1)] = NP (per PCP theorem) ;  PCP[poly(n), O(1)]] = PCP(poly(n), poly(n)] = NEXP; or am i being redundant? :)
Ahmed Masud
CC BY-SA 3.0
2011-12-16T17:26:16.353Z
the policy here is not to help on homework, isn't it?
Sasho Nikolov
CC BY-SA 3.0
2011-12-16T18:13:01.127Z
That is correct.
Suresh Venkat
CC BY-SA 3.0
2011-12-16T22:01:04.773Z
Proving MIP=NEXP assuming NEXP=PCP(poly,const) is indeed an exercise, unlike your original question.
Tsuyoshi Ito
CC BY-SA 3.0
2013-05-29T05:22:23.060Z
We can't migrate this question to [cs.se] since it is too old. We should either close it as off-topic or answer it. I personally don't have a preference.
Kaveh
<cc.complexity-theory><pcp><nexp>
More legent proof of MIP=NEXP using the PCP theorem
dan
# More legent proof of MIP=NEXP using the PCP theorem

(Asked by: username_0 on 2011-12-12)

> Can we prove $\mathsf{MIP}=\mathsf{NEXP}$ using the PCP theorem $\mathsf{NP}=\mathsf{PCP(log(n),O(1))}$ as a shortcut?

$\mathsf{MIP}$ is the class of languages with multi-prover interactive proof systems.

---

Here is what I know:

Intuitively, it's hard for me to see how another prover adds any power to the protocol. The only way I can think of is to somehow make the two provers contradict each other to easily detect false positives.

I have come across the implication that $\mathsf{NEXP}=\mathsf{PCP}(n^{O(1)},O(1))$ and tried to use it, but I fail to understand why the following protocol doesn't work for a single prover:

1. ask the prover for the length of the exponential certificate.
2. repeat C times: (for some constant C which we know exists due to the above theorem).

   * generate a random index to the certificate and ask the prover to hand over the bits from the given location.
   * verify that the certificate is still valid, otherwise reject.
3. after C successful queries - accept.

Obviously there is some defect in this protocol because $\mathsf{IP}=\mathsf{PSPACE}$ and it has not been proven that $\mathsf{PSPACE}=\mathsf{NEXP}$ (which would be implied if the protocol is correct).

Also the following paper seems relevant:

* Laszlo Babai, Lance Fortnow and Carsten Lund, "[Nondeterministic exponential time has two-prover interactive protocols](http://portal.acm.org/citation.cfm?id=1398742)", 1990.

---

### Note:

The question was a homework but was posted more than a year ago.

**Tags:** cc.complexity-theory, pcp, nexp
> **Comments:**
> **username_1**: Why do you "need" to write this proof ? is it a homework question ?  
> **username_2**: The way the question is stated sounds as if it is a homework.  But personally I fail to see how the blackbox statement NP=PCP(log,const) implies MIP=NEXP (probably because I am just too dumb).  
> **username_3**: It is certainly true that NP=PCP(log, const) implies that multiple-prover interactive proofs with logarithmic communication is NP. You then have to make everything exponentially bigger to get MIP=NEXP; I don't know how many technical details are involved in this step.  
> **username_2**: Making my previous comment more precise, I am pretty sure that no easy proof of a stronger implication NP=PCP(log,const)⇒NEXP=PCP(poly,const) is known (see [Meir 2011](http://eccc.hpi-web.de/report/2011/104/)).  But I will not rule out the possibility that there is an easy way to prove NP=PCP(log,const)⇒MIP=NEXP without proving the stronger implication, although I cannot see how.  
> **username_4**: why does this question have three negative votes? Because of the word "need" I am thinking, and the lack of subsequent participation by the asker. Change "need" to "want" and this seems clearly on topic for the site.  
> **username_2**: @Aaron: In fact, there are other deficiencies in the question.  (1) The question contains some ambitious statement as an “assumption” and therefore it is hard to understand what the question really is.  (2) “A 40 page long article proving the required (for the first time, I believe)” is a terrible way to cite a paper.  
> **username_4**: @Tsuyoshi: I agree. If the asker had returned to the question, those points hopefully would have been cleaned up.  
> **username_3**: The protocol you give doesn't work because the prover could cheat by reporting different results for the bit at location 2, depending on which location 1 you asked him for. If you have two provers, this can't happen. I find writing down an explicit cheating strategy for the prover to be quite hard for some protocols, but I assume such a strategy must exist.  
> **username_5**: PCP[O(log n), O(1)] = NP (per PCP theorem) ;  PCP[poly(n), O(1)]] = PCP(poly(n), poly(n)] = NEXP; or am i being redundant? :)  
> **username_6**: the policy here is not to help on homework, isn't it?  
> **username_1**: That is correct.  
> **username_2**: Proving MIP=NEXP assuming NEXP=PCP(poly,const) is indeed an exercise, unlike your original question.  
> **username_7**: We can't migrate this question to [cs.se] since it is too old. We should either close it as off-topic or answer it. I personally don't have a preference.  

---

## 0 answers

