DIMACS TR: 93-79

Random Debaters and the Hardness of Approximating Stochastic Functions



Authors: Anne Condon, Joan Feigenbaum, Carsten Lund, & Peter Shor

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 0, 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 ([Condon et al., Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 304--315]). In this paper, we restrict attention to RPCDS's, which are PCDS's in which Player 0 follows a very simple strategy: On each turn, Player 0 chooses uniformly at random from the set of legal moves. We prove the following result.

Theorem: L has an RPCDS in which the verifier flips O(log n) coins and reads O(1) bits of the debate if and only if L is in PSPACE.

This new characterization of PSPACE is used to show that certain stochastic PSPACE-hard functions are as hard to approximate closely as they are to compute exactly. Examples of such functions include optimization versions of Dynamic Graph Reliability, Stochastic Satisfiability, Mah-Jongg, Stochastic Coloring, Stochastic Generalized Geography, and other ``games against nature'' of the type introduced in [Papadimitriou, J. Comput. System Sci., 31 (1985), pp.~288--301].

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-79.ps


DIMACS Home Page