Random Debaters and the Hardness of Approximating Stochastic Functions (Extended Abstract)
Anne Condont, Joan Feigenbaum, Carsten Lund · 1994
A random probabilistically checkable debate system (RPCDS) for a language L consists of a probabilistic polynomial-time verifier V and a debate between Player 1, who aims to prove that the input z is in L, and Player 0, who selects a move uniformly at random from the set of legal moves. This model is a natural restriction of the PCDS model ([Condon et al., Proc. 25th ACM Symposium on Theory of Computing, 1993, pp. 304-3151). We show that: Theorem: L has an RPCDS in which the verifier flips O(1ogn) coins and reads O(1) bits of the debate if and only if L is in PSPACE. Using this new characterization of PSPACE, we show that certain stochastic PSPACEhard functions are as hard to approximate closely as they are to compute exactly. Examples 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-3011.