  We introduce a model of probabilistic debate checking, where a silent
resource-bounded verifier reads a dialogue about the membership of the 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 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 of logarithmic
space and polynomial time. It turns out that constant-space verifiers, which
can only check complete-information debates for regular languages
deterministically, can check for membership in any language in P when allowed
to use a constant number of random bits. Similar increases also occur for zero-
and partial- information debates, from NSPACE(n) to PSPACE, and from E to
EXPTIME, respectively. Adding logarithmic space to these constant-randomness
verifiers does not change their power. When logspace debate checkers are
restricted to run in polynomial time without a bound on the number of random
bits, the class of debatable languages equals PSPACE for all debate types. We
also present a result on the hardness of approximating the quantified max word
problem for matrices that is a corollary of this characterization.
