Alternation in interaction

The traditional studies of multi-prover interactive proof systems have conc entrated on cooperating provers. These are systems in which a verifier inte racts with a set of provers who collaborate in their attempt to convince th e verifier that a word omega is in a prespecified language L. Results on pr obabilistically checkable proofs coupled with parallel repetition technique s characterize NP in terms of multi-prover proof systems: languages in NP c an be verified through a one-round interaction with two cooperating provers using limited randomness and communication. Less attention has been paid to the study of competition in this complexity -theoretic setting of interactive proof systems. We consider, for example, one-round proof systems where the first prover is trying to convince the ve rifier to accept and the second prover is trying to convince the verifier t o reject. We build into these proof systems a (crucial) asymmetry between t he provers, analogous to quantifier alternation. We show that such proof sy stems capture, with restrictions on communication and randomness, languages in NP. We generalize this model by defining alternating prover proof syste ms which we show characterize each level of the polynomial hierarchy. Alter nating oracle proof systems are also examined. The main contribution of this work is the first exact characterization of t he polynomial hierarchy in terms of interactive (prover) proof systems.