DIMACS TR: 93-79
Random Debaters and the Hardness of Approximating
Authors: Anne Condon, Joan Feigenbaum, Carsten Lund, & Peter Shor
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
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:
DIMACS Home Page