<p>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?</p>

CC BY-SA 4.0
2020-05-12T21:49:15.733Z
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.
Yonatan N
CC BY-SA 4.0
2020-05-12T22:32:57.583Z
See Theorem 4 (proof in Section 5) of the [BKM88] paper introducing the class MIP.
https://dl.acm.org/doi/10.1145/62212.62223
(also availablle, without paywall, [here](http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC08/BGKW88.pdf))
Clement C.
<complexity-classes><interactive-proofs>
Why can MIP be restricted to just two provers?
lacker
# Why can MIP be restricted to just two provers?

(Asked by: username_0 on 2020-05-12)

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?

**Tags:** complexity-classes, interactive-proofs
> **Comments:**
> **username_1**: 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.  
> **username_2**: See Theorem 4 (proof in Section 5) of the [BKM88] paper introducing the class MIP. https://dl.acm.org/doi/10.1145/62212.62223 (also availablle, without paywall, [here](http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC08/BGKW88.pdf))  

---

## 0 answers

