On the power of multi-power interactive protocols
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 156-161
- https://doi.org/10.1109/sct.1988.5275
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: