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 .
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.