Alternation in interaction
Marcos A. Kiwi, Carsten Lund, Alexander C. Russell, Daniel A. Spielman, Ravi Sundaram · 2002
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 /spl Sigmasub k-1sup P/. Alternating oracle proof systems are also examined.>