The complexity of debate checking

We introduce a model of probabilistic debate checking, where a silent resource-bounded verifier 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 verifiers 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 verifiers for any desired error bound when we loosen the randomness bound. We also examine the power of debate checking by time-bounded verifiers and show that no amount of randomness can help a time-bounded verifier to outperform its deterministic counterpart. However, we show that randomness does seem to help when we further constrain these time-bounded verifiers to use only logarithmic space in the order of their time bound. Additionally, in case of logspace and polynomial-time verifiers, we show that logarithmic randomness is sufficient to check complete- and partial-information debates for the languages in PSPACE. Finally, we show that any language having debates checkable by logspace polynomial-time verifiers can be reduced to the quantified max word problem for matrices, which allows us to present a result on the hardness of approximating this problem.