Arthur–Merlin protocol

Builds on Interactive proof system P Formal language

Definition

An Arthur–Merlin protocol is an interactive proof system of the following kind. Every message of the verifier, Arthur, is a fresh uniform random string. Arthur's final decision is a deterministic polynomial-time function of the input and all messages. The prover is called Merlin.

Let $L \subseteq \set{0,1}^*$ be a language. In the conditions below, $r$ is uniform in $\set{0,1}^{q(\abs{x})}$ and $m$ ranges over $\set{0,1}^{q(\abs{x})}$ . The language $L$ is in the class AM if there are a polynomial $q$ and a language $R$ in P such that:

if $x \in L$ , then $\Pr_r[\exists m \ (x, r, m) \in R] \ge 2/3$ ;
if $x \notin L$ , then $\Pr_r[\exists m \ (x, r, m) \in R] \le 1/3$ .

The class MA is defined in the same way with Merlin's message first. So $L \in \mathrm{MA}$ if there are $q$ and $R$ as above with the following two properties. If $x \in L$ , then $\exists m \ \Pr_r[(x, r, m) \in R] \ge 2/3$ . If $x \notin L$ , then $\forall m \ \Pr_r[(x, r, m) \in R] \le 1/3$ .

Remarks

Example: every language in NP is in MA, and so in AM. If $x \in L$ if and only if $\exists m \ (x, m) \in R_0$ with $R_0 \in \mathrm{P}$ , let $R = \set{(x, r, m) : (x, m) \in R_0}$ , which ignores $r$ ; both clauses hold with probabilities $1$ and $0$ .

Non-example: the protocol for graph non-isomorphism in which Arthur hides his choice of graph is not an Arthur–Merlin protocol, because its random bits are private. Graph non-isomorphism is nevertheless in AM, through a different protocol based on set lower bounds with hash functions.

Babai showed that every protocol with a constant number of rounds of public coins gives the class AM. Goldwasser and Sipser showed that private coins can be replaced by public coins with two more rounds, so the classes defined by a constant number of rounds coincide with AM.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`WQJQBFBSC8`
URI	`m2://WQJQBFBSC8`
Kind	definition
Writing	W0 stub
MSC	68Q10, 68Q15, 68Q87
Defines	Arthur–Merlin protocol
Uses	Interactive proof system, P, Formal language
Changed	3 November 2026

Arthur–Merlin protocol

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here