Arthur–Merlin protocol

<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, an Arthur–Merlin protocol, introduced by Babai (1985), is an <a href="/facts/Interactive_proof_system/rDB0agR9">interactive proof system</a> in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too). Goldwasser & Sipser (1986) proved that all (formal) <a href="/facts/Formal_language/crDTyP8q">languages</a> with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins.
</p><p>Given two participants in the protocol called Arthur and Merlin respectively, the basic assumption is that Arthur is a standard computer (or verifier) equipped with a <a href="/facts/Random_number_generation/RtXEfbzd">random number generating device</a>, while Merlin is effectively an <a href="/facts/Oracle_(computer_science)/6ScMuvvY">oracle</a> with infinite computational power (also known as a prover). However, Merlin is not necessarily honest, so Arthur must analyze the information provided by Merlin in response to Arthur's queries and decide the problem itself. A problem is considered to be solvable by this protocol if whenever the answer is "yes", Merlin has some series of responses which will cause Arthur to accept at least 2⁄3 of the time, and if whenever the answer is "no", Arthur will never accept more than 1⁄3 of the time. Thus, Arthur acts as a probabilistic polynomial-time verifier, assuming it is allotted polynomial time to make its decisions and queries.
</p>

Arthur–Merlin protocol open-in-new

Arthur–Merlin protocol