Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes (Q1106840)

Exceedingly long proofs or computer-assisted proofs address the question that there might be a positive probability that a proof is in error. Such facts emphasize the role played in mathematics by the verifier (vs. the prover). The paper deals with the problem of formalization of the notion of efficient provability by overwhelming statistical evidence. A randomized proof combines the nondeterministic nature of a classical proof system with the randomization performed by probabilistic algorithms. The main example is Arthur-Merlin protocol which is used to obtain a hierarchy of complexity classes ``just above NP''.