On the power of multi-power interactive protocols

Lance Fortnow, John Rompel, M. Sipser

1988 · 130 citations · 13 references

Concepts

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

References

13