Title :
Alternation in interaction
Author :
Kiwi, M. ; Lund, C. ; Russell, A. ; Spielman, D. ; Sundaram, R.
Author_Institution :
Dept. of Appl. Math., MIT, Cambridge, MA, USA
fDate :
28 Jun- 1 Jul 1994
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 recognized 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 Σk-1P. Alternating oracle proof systems are also examined
Keywords :
automata theory; computational complexity; decidability; formal languages; theorem proving; NEXPTIME; alternating sequence; competing-prover one-round interactive proof systems; languages; oracle proof systems; undecidability; Books; Computer science; Contracts; Marine vehicles; Mathematical model; Mathematics; Polynomials; Protocols; Voting;
Conference_Titel :
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location :
Amsterdam
Print_ISBN :
0-8186-5670-0
DOI :
10.1109/SCT.1994.315795
