We study the class of languages, denoted by @math , which have @math -prover games where each prover just sends a bit, with completeness @math and soundness error @math . For the case that @math (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson ( Computational Complexity'02 ) demonstrate that @math exactly characterizes languages having 1-bit proof systems with"non-trivial" soundness (i.e., @math ). We demonstrate that for the case that @math , 1-bit @math -prover games exhibit a significantly richer structure: + (Folklore) When @math , @math ; + When @math , @math ; + When @math , @math ; + For @math and sufficiently large @math , @math ; + For @math , @math . As such, 1-bit @math -prover games yield a natural "quantitative" approach to relating complexity classes such as @math , @math , @math , @math , and @math . We leave open the question of whether a more fine-grained hierarchy (between @math and @math ) can be established for the case when @math .
The work most closely related to our is the work by Goldreich, Vadhan and Wigderson @cite_3 mentioned above which in turn builds on a work by Goldreich and H stad @cite_14 ; just as we do, both these works investigate the complexity of interactive proofs with laconic'' provers. We have taken the question to an extreme in one direction (namely we focus only on provers that send a single bit); on the other hand, we have generalized the question by considering multi-prover interactive proofs, rather than just a single prover (as is the main focus in the above-mentioned works).
@cite_14 @cite_3
2040438296 2038202352
Abstract We investigate the computational complexity of languages which have interactive proof systems of bounded message complexity. In particular, denoting the length of the input by n , we show that • If L has an interactive proof in which the total communication is bounded by c ( n ) bits then L can be recognized by a probabilistic machine in time exponential in rmO ( c ( n ) + log ( n )). • If L has a public-coin interactive proof in which the prover sends c ( n ) bits then L can be recognized by a probabilistic machine in time exponential in rmO ( c ( n ) · log ( c ( n )) + log ( n )). • If L has an interactive proof in which the prover sends c ( n ) bits then L can be recognized by a probabilistic machine with an NP-oracle in time exponential in rmO ( c ( n ) · log ( c ( n )) + log ( n )). We continue the investigation of interactive proofs with bounded communication, as initiated by Goldreich & Hastad (1998). Let L be a language that has an interactive proof in which the prover sends few (say b) bits to the verifier. We prove that the complement L has a constant-round interactive proof of complexity that depends only exponentially on b. This provides the first evidence that for NP- complete languages, we cannot expect interactive provers to be much more "laconic" than the standard NP proof. When the proof system is further restricted (e.g., when b = 1, or when we have perfect completeness), we get significantly better upper bounds on the complexity of L.