Playing a Prisoner's Delemma Game in a MIP proving system. > [!theorem] MIP=MIP[2] > up to polynomial blowups in $\mathcal{V}$ 's runtime, 2-prover MIPs are just as expressive as $k$-prover MIPs, for any $k=\operatorname{poly}(n)$ 2 prover 的表达能力和k prover是一样的，只是verifier慢polynomial倍？慢还是快？ the presence of a second prover (who does not know V’s messages to the first prover) prevents the first prover from behaving in this adaptive manner MIPs are more expressive than IPs Allowing the prover to behave adaptively gives the prover more power to break soundness. since allowing adaptivity on the part of the prover means allowing “more expressive” prover strategies, prover adaptivity leads to efficient proof systems for more challenging problems. In fact, the opposite is true. Hence, allowing the prover to behave adaptively actually weakens the class of problems that have proof systems with an efficient verifier. ## 一个额外的证明者能带来什么？ IP中，一个证明者，==可以==是adaptive的。（$\mathcal{P}$ 's response to the $i$ th message $m_i$ sent from $\mathcal{V}$ is ==allowed== to depend on the preceding $i-1$ messages.） 而在第二证明者存在的MIP中，每一个证明者都==不可能==是adaptive的！因为每个证明者都==不知道==$\mathcal{V}$ 给其他证明者发送的挑战。 > [!note]- MIP = the class of languages satisfied by polynomial time randomized *oracle machines* > [FRS88]. Let $\mathcal{L}$ be a language, and $M$ a probabilistic polynomial time oracle Turing Machine. Let $M^{\mathcal{O}}$ denote $M$ when given query access to oracle $\mathcal{O}$. Suppose that $x \in \mathcal{L} \Longrightarrow \exists$ an oracle $\mathcal{O}$ such that $M^{\mathcal{O}}$ accepts $x$ with probability 1 , and $x \notin \mathcal{L} \Longrightarrow \forall$ oracles $\mathcal{O}, M^{\mathcal{O}}$ rejects $x$ with probability at least $2 / 3$. Then there is a 2-prover MIP for $\mathcal{L}$. "三人成虎"：增加不关联的prover可以使得verifier相信本来是假的statement，也就是增加soundness error。