Bibliographic Information:
Computational Complexity, 9(3-4):202-246, 2000
Extended abstract appeared in
Proceedings of the 9th
Annual IEEE Conference on Structure in Complexity Theory,
1994, pp. 294-303.
To view a compressed version, click here.
Abstract
We study competing-prover one-round interactive
proof systems.
We show that one-round proof systems in which
the first prover is trying to convince a
verifier to accept and the second prover is trying
to make the verifier reject
recognize languages in $\NEXPTIME$, and,
with restrictions on communication and randomness,
languages in $\NP$.
We extended the restricted model to an alternating
sequence of $k$ competing provers,
which we show characterizes $\Sigma_{k-1}^{P}$.
Alternating oracle proof systems are also examined.
To view the paper, click here.
Daniel A. Spielman
Last modified: Fri Aug 29 15:42:39 EDT 2003