A simple characterization of the power of the multipower model in terms of probabilistic oracle Turing machines is given. It is shown that languages that have single-prover interactive protocols also have two prover-bounded round protocols and that languages that have multiprover interactive protocols have two prover protocols and three prover-bounded round protocols. An oracle is given relative to which there exists a co-NP language, that is not accepted by any multiprover interactive protocol.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
No takes yet. Share an insight, caveat, or question.
Fortnow et al. (1988) studied this question.