As the authors state, “Interactive proof systems are two-party randomized protocols through which a computationally unbounded prover can convince a probabilistic polynomial-time verifier of the membership of a common input in a predetermined language.”
The languages in PSPACE have interactive proof systems. If we restrict the amount of communication between prover and verifier, say to b(n) bits, which the prover can send to the verifier on inputs of length n, we arrive at so-called laconic provers. The authors investigate the classes of languages characterized by various types of laconic provers. In particular, they show that, if a language has a laconic interactive proof of perfect completeness (namely, zero error probability on YES instances), then it is in coNTIME(T), where T(n) =2b(n) poly(n). Thus, unless NP=coNP, NP-complete languages cannot have interactive proof systems of perfect completeness, in which the prover sends logarithmically many bits. Furthermore, the authors show that, if a language has a laconic interactive proof, in which the prover sends a single bit, then it has a statistical zero-knowledge interactive proof.
