Chicago Journal of Theoretical Computer Science

Volume 1995

Article 4

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.

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

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.

DOI: 10.4086/cjtcs.1995.004
[] Article 3 [] Volume 1996, Article 1
[back] Volume 1995 [back] Published articles
[CJCTS home]

Last modified: 24 March 1997