On the power of many one-bit provers
Per Austrin, Johan Håstad, Rafael Pass · 2013
We study the class of languages, denoted by MIP[k, 1-ε, s], which have k-prover games where each prover just sends a single bit, with completeness 1-ε and soundness error s. For the case that k=1 (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson (Computational Complexity'02) demonstrate that SZK exactly characterizes languages having 1-bit proof systems with "non-trivial" soundness (i.e., 1/2 < s ≤ 1-2ε). We demonstrate that for the case that k ≥ 2, 1-bit k-prover games exhibit a significantly richer structure: (Folklore) When s ≤ 1/2k - ε, MIP[k, 1-ε, s] = BPP; When 1/2k + ε ≤ s < 2/2k -ε, MIP[k, 1-ε, s] = SZK; When s ≥ 2/2k + ε, AM ⊆ MIP[k, 1-ε, s]; For s ≤ 0.62 k/2k and sufficiently large k, MIP[k, 1-ε, s] ⊆ EXP; For s ≥ 2k/2k, MIP[k, 1, 1-ε, s] = NEXP.