DIMACS TR: 93-10
Probabilistically Checkable Debate Systems and Approximation
Algorithms for PSPACE-Hard Functions
Authors: Anne Condon, Joan Feigenbaum, Carsten Lund and Peter Shor
ABSTRACT
We initiate an investigation of ``probabilistically checkable debate
systems'' (PCDS's), a natural generalization of the probabilistically
checkable proof systems studied in, e.g., [Babai et al., Proc. 23rd
ACM Symp. Theory of Computing, 1991, pp. 21-31], [Feige et al., Proc.
32nd IEEE Symp. Foundations of Computer Science, 1991, pp. 2-12],
[Arora et al., Proc. 33rd IEEE Symp. Foundations of Computer Science,
1992, pp. 2-13], [Arora et al., Proc. 33rd IEEE Symp. Foundations of
Computer Science, 1992, pp. 14-23]. A 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. We show that there is a PCDS
for L in which V flips O(log n) random coins and reads O(1) bits of
the debate if and only if L is in PSPACE. This characterization of
PSPACE is used to show that certain PSPACE-hard functions are as
hard to approximate as they are to compute exactly.
These results were presented in preliminary form at the 25th ACM
Symposium on Theory of Computing, San Diego CA, May 1993.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-10.ps
DIMACS Home Page