In several places I see it referred to that the MIP class can be assumed to be two interactive provers that don't communicate with each other, rather than any polynomial number of provers. Why are these classes equivalent? Is there a way to take an algorithm for proving membership with k provers, and turn that into an algorithm that works with only 2 provers, with blowup polynomial in k?

  • 6
    $\begingroup$ You can reduce any instance with $k$ provers down to just $2$. Call the provers $A$ and $B$. Have $A$ simulate the $k$ different provers in the original protocol, and hold the entire simulated multi-prover conversation with just $A$. Now for a random simulated prover $p$, have $B$ simulate $p$'s place in the previous conversation, and ascertain that both $A$ and $B$ simulate $p$ identically. If $A$'s simulation "cheated" by leaking information to $p$, then this will catch it with probability $\geq 1/k$. Repeat this process $\textrm{poly}(k,n)$ times with fresh bits to get sufficient soudnness. $\endgroup$ – Yonatan N May 12 '20 at 21:49
  • 3
    $\begingroup$ See Theorem 4 (proof in Section 5) of the [BKM88] paper introducing the class MIP. dl.acm.org/doi/10.1145/62212.62223 (also availablle, without paywall, here) $\endgroup$ – Clement C. May 12 '20 at 22:32

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.