The complexity of debate checking

Abstract

We introduce a model of probabilistic debate checking, where a silent resourcebounded veri er reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. Our model combines and generalizes the concepts of one-way interactive proof systems, games of incomplete information, and probabilistically checkable complete-information debate systems. We consider debates of partial- and zero-information, where the prover is prevented from seeing some or all of the messages of the refuter, as well as those of complete-information. The classes of languages with debates checkable by veri ers operating under severe bounds on the time, memory, and randomness are studied. We give full characterizations of versions of these classes corresponding to simultaneous bounds of O(1) space and O(1) random bits, and logarithmic space and O(1) random bits. We further examine the power of constant-space model by giving lower bounds for the classes of languages checkable by such veri ers for any desired error bound when we loosen the randomness bound. We also examine the power of debate checking by time-bounded veri ers and show that no amount of randomness can help a timebounded veri er to outperform its deterministic counterpart. However, we show that randomness does seem to help when we further constrain these time-bounded veri ers to use only logarithmic space in the order of their time bound. Additionally, in case of logspace and polynomial-time veri ers, we show that logarithmic randomness is su - cient to check complete- and partial-information debates for the languages in PSPACE. Finally, we show that any language having debates checkable by logspace polynomialtime veri ers can be reduced to the quanti ed max word problem for matrices, which allows us to present a result on the hardness of approximating this problem.