Published by MIT Press. Copyright 1995 Massachusetts Institute of Technology.

Your institution may already be a
subscriber to CJTCS. If not,
**please subscribe**
for legitimate access to all journal articles.

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

DOI: 10.4086/cjtcs.1995.004

Article 3 Volume 1996, Article 1

Volume 1995 Published articles

Article 3 Volume 1996, Article 1

Volume 1995 Published articles

Last modified: 24 March 1997