1988 · 130 citations · 13 references
ComputingComputer ScienceMathematicsAlgorithmsCryptographyTheory Of ComputationComputability TheoryComputational ModelsInteractive Proof SystemsTuring MachinesOracle Turing MachinesProbabilistic Proof SystemsProbabilistic Turing MachinesProof Systems
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>
13
Trading group theory for randomness
László Babai · 1985 · 782 citations
Multi-prover interactive proofs: how to remove intractability
Michael Ben-Or, Shafi Goldwasser, Joe Kilian · 1988 · 484 citations