Random Debators and the Hardness of Approximating Stochastic Functions (Extended Abstract)

A probabilistically checkable debate system (PCDS) for a language L consists of a probabilistic polynomial-time verifier V and a debate between Player 1, who claims that the input x is in L, and Player O, who claims that the input x is not in L. It is known that there is a PCDS for L in which V flips O(log n) coins and reads O(1) bits of the debate if and only if L is in PSPACE (cf.[Condon et al., Proc. 25th ACM Symposium on Theory of Computing, 1993]). In this paper, we restrict attention to RPCDS's, which are PCDS's in which Player O follows a very simple strategy; Whenever it is his turn, he chooses uniformly at random from the set of legal moves.