CJTCS Volume 1995 Article 4

Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions

Anne Condon ( University of Wisconsin ), Joan Feigenbaum ( AT&T Bell Laboratories ), Carsten Lund ( AT&T Bell Laboratories ), and Peter W. Shor ( AT&T Bell Laboratories ) 19 October 1995

Abstract

We initiate an investigation of probabilistically checkable debate systems (PCDS), a natural generalization of probabilistically checkable proof systems (PCPS). 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 closely as they are to compute exactly.

• Preformatted versions of the article
  • DVI: Part of Figure 1 is presented as encapsulated PostScript. With most WWW browsers, if you view the DVI file directly, you will not see that portion of the figure. In order to view the DVI version, download both files below. Store them in the same directory, and name the encapsulated PostScript file " c9504f1.eps ".
    • DVI (137,948 bytes)
    • Encapsulated PostScript used in Figure 1 ( c9504f1.eps , 5,658 bytes)
  • PostScript (381,930 bytes)
  • PDF (365,788 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX ( cj95-04.tex , 102,958 bytes)
  • BIBTeX ( cj95-04.bib , 6,956 bytes)
  • Encapsulated PostScript used in Figure 1 ( c9504f1.eps , 5,658 bytes)
  • Parameter settings for custom formatting ( cjropts.tex , 353 bytes)
  • Self citation in BIBTeX (407 bytes)
• Online discussion
• Instructions for Readers

---

Article 3 Volume 1996, Article 1
Volume 1995 Published articles

Last modified: 24 March 1997