3
$\begingroup$

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:


Note:

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

$\endgroup$
  • 6
    $\begingroup$ Why do you "need" to write this proof ? is it a homework question ? $\endgroup$ – Suresh Venkat Dec 13 '11 at 0:28
  • 3
    $\begingroup$ 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). $\endgroup$ – Tsuyoshi Ito Dec 13 '11 at 3:46
  • 3
    $\begingroup$ 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. $\endgroup$ – Peter Shor Dec 13 '11 at 12:09
  • 6
    $\begingroup$ 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. $\endgroup$ – Aaron Sterling Dec 13 '11 at 14:42
  • 5
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Dec 14 '11 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.