On the Power of Many One-Bit Provers

Abstract

We study the class of languages, denoted by $\MIP[k, 1-ε, s]$, which have $k$-prover games where each prover just sends a \emph{single} bit, with completeness $1-\epsilon$ and soundness error $s$. For the case that $k=1$ (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson ({\em Computational Complexity'02}) demonstrate that $\SZK$ exactly characterizes languages having 1-bit proof systems with"non-trivial" soundness (i.e., $1/2<s\le 1-2\epsilon$). We demonstrate that for the case that $k\ge 2$, 1-bit $k$-prover games exhibit a significantly richer structure: + (Folklore) When $s\le \frac{1}{2^k}-\epsilon$, $\MIP[k, 1-ε, s] = \BPP$; + When $\frac{1}{2^k}+\epsilon \le s<\frac{2}{2^k}-\epsilon$, $\MIP[k, 1-ε, s] = \SZK$; + When $s\ge \frac{2}{2^k}+\epsilon$, $\AM \subseteq \MIP[k, 1-ε, s]$; + For $s\le 0.62k/2^k$ and sufficiently large $k$, $\MIP[k, 1-ε, s] \subseteq \EXP$; + For $s\ge 2k/2^k$, $\MIP[k, 1, 1-ε, s] = \NEXP$. As such, 1-bit $k$-prover games yield a natural "quantitative" approach to relating complexity classes such as $\BPP$,$\SZK$,$\AM$, $\EXP$, and $\NEXP$. We leave open the question of whether a more fine-grained hierarchy (between $\AM$ and $\NEXP$) can be established for the case when $s\ge \frac{2}{2^k}+\epsilon$.