Hubbry Logo
Arthur–Merlin protocolArthur–Merlin protocolMain
Open search
Arthur–Merlin protocol
Community hub
Arthur–Merlin protocol
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Arthur–Merlin protocol
Arthur–Merlin protocol
Arthur–Merlin protocol
View on Wikipedia
from Wikipedia

In computational complexity theory, an Arthur–Merlin protocol, introduced by Babai (1985), is an interactive proof system 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) languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins.

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 random number generating device, while Merlin is effectively an oracle 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.

MA

[edit]

The simplest such protocol is the 1-message protocol where Merlin sends Arthur a message, and then Arthur decides whether to accept or not by running a probabilistic polynomial time computation. (This is similar to the verifier-based definition of NP, the only difference being that Arthur is allowed to use randomness here.) Merlin does not have access to Arthur's coin tosses in this protocol, since it is a single-message protocol and Arthur tosses his coins only after receiving Merlin's message. This protocol is called MA. Informally, a language L is in MA if for all strings in the language, there is a polynomial sized proof that Merlin can send Arthur to convince him of this fact with high probability, and for all strings not in the language there is no proof that convinces Arthur with high probability.

Formally, the complexity class MA is the set of decision problems that can be decided in polynomial time by an Arthur–Merlin protocol where Merlin's only move precedes any computation by Arthur. In other words, a language L is in MA if there exists a polynomial-time deterministic Turing machine M and polynomials p, q such that for every input string x of length n = |x|,

  • if x is in L, then
  • if x is not in L, then

The second condition can alternatively be written as

  • if x is not in L, then

To compare this with the informal definition above, z is the purported proof from Merlin (whose size is bounded by a polynomial) and y is the random string that Arthur uses, which is also polynomially bounded.

AM

[edit]

The complexity class AM (or AM[2]) is the set of decision problems that can be decided in polynomial time by an Arthur–Merlin protocol with two messages. There is only one query/response pair: Arthur tosses some random coins and sends the outcome of all his coin tosses to Merlin, Merlin responds with a purported proof, and Arthur deterministically verifies the proof. In this protocol, Arthur is only allowed to send outcomes of coin tosses to Merlin, and in the final stage Arthur must decide whether to accept or reject using only his previously generated random coin flips and Merlin's message.

In other words, a language L is in AM if there exists a polynomial-time deterministic Turing machine M and polynomials p, q such that for every input string x of length n = |x|,

  • if x is in L, then
  • if x is not in L, then

The second condition here can be rewritten as

  • if x is not in L, then

As above, z is the alleged proof from Merlin (whose size is bounded by a polynomial) and y is the random string that Arthur uses, which is also polynomially bounded.

The complexity class AM[k] is the set of problems that can be decided in polynomial time, with k queries and responses. AM as defined above is AM[2]. AM[3] would start with one message from Merlin to Arthur, then a message from Arthur to Merlin and then finally a message from Merlin to Arthur. The last message should always be from Merlin to Arthur, since it never helps for Arthur to send a message to Merlin after deciding his answer.

Properties

[edit]
A diagram showcasing the relationships of MA and AM with other complexity classes described in the article.
Known relationships of MA and AM with other complexity classes. An arrow from class A to class B means A is a subset of B.
  • Both MA and AM remain unchanged if their definitions are changed to require perfect completeness, which means that Arthur accepts with probability 1 (instead of 2/3) when x is in the language.[1]
  • For any constant k ≥ 2, the class AM[k] is equal to AM[2]. If k can be polynomially related to the input size, the class AM[poly(n)] is equal to the class, IP, which is known to be equal to PSPACE and is widely believed to be stronger than the class AM[2].
  • MA is contained in AM, since AM[3] contains MA: Arthur can, after receiving Merlin's certificate, flip the required number of coins, send them to Merlin, and ignore the response.
  • It is open whether AM and MA are different. Under plausible circuit lower bounds (similar to those implying P=BPP), they are both equal to NP.[2]
  • AM is the same as the class BP⋅NP where BP denotes the bounded-error probabilistic operator. Also, ( also written as ExistsBPP) is a subset of MA. Whether MA is equal to is an open question.
  • The conversion to a private coin protocol, in which Merlin cannot predict the outcome of Arthur's random decisions, will increase the number of rounds of interaction by at most 2 in the general case. So the private-coin version of AM is equal to the public-coin version.
  • MA contains both NP and BPP. For BPP this is immediate, since Arthur can simply ignore Merlin and solve the problem directly; for NP, Merlin need only send Arthur a certificate, which Arthur can validate deterministically in polynomial time.
  • Both MA and AM are contained in the polynomial hierarchy. In particular, MA is contained in the intersection of Σ2P and Π2P and AM is contained in Π2P. Even more, MA is contained in subclass SP
    2    ,[3] a complexity class expressing "symmetric alternation". This is a generalization of Sipser–Lautemann theorem.
  • AM is contained in NP/poly, the class of decision problems computable in non-deterministic polynomial time with a polynomial size advice. The proof is a variation of Adleman's theorem.
  • MA is contained in PP; this result is due to Vereshchagin.[4]
  • MA is contained in its quantum version, QMA.[5]
  • AM contains the problem of deciding if two graphs are not isomorphic. The protocol using private coins is the following and can be transformed to a public coin protocol. Given two graphs G and H, Arthur randomly chooses one of them, and chooses a random permutation of its vertices, presenting the permuted graph I to Merlin. Merlin has to answer if I was created from G or H. If the graphs are nonisomorphic, Merlin will be able to answer with full certainty (by checking if I is isomorphic to G). However, if the graphs are isomorphic, it is both possible that G or H was used to create I, and equally likely. In this case, Merlin has no way to tell them apart and can convince Arthur with probability at most 1/2, and this can be amplified to 1/4 by repetition. This is in fact a zero knowledge proof.
  • If AM contains coNP then PH = AM. This is evidence that graph isomorphism is unlikely to be NP-complete, since it implies collapse of polynomial hierarchy.
  • It is known, assuming ERH, that for any d the problem "Given a collection of multivariate polynomials each with integer coefficients and of degree at most d, do they have a common complex zero?" is in AM.[6]

References

[edit]

Bibliography

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Arthur–Merlin protocol

View on Grokipedia
from Grokipedia
The Arthur–Merlin protocol, also known as an Arthur-Merlin game, is a model of interactive proof in featuring a two-round interaction between a probabilistic polynomial-time verifier named Arthur and an unbounded prover named Merlin, where Arthur uses public to verify statements about an input, and Merlin attempts to convince Arthur of their truth with high probability if true and fails with high probability if false. This public-coin protocol, in which the verifier's random bits are shared openly, was first introduced by in 1985 as a tool to replace intricate group-theoretic arguments with randomized verification techniques for problems like matrix group membership testing. In the protocol, Arthur generates random bits publicly and sends them to Merlin, who responds with a message; Arthur accepts if the interaction satisfies a predetermined verification predicate, ensuring perfect completeness (acceptance with probability 1 if the input is in the language) and statistical soundness (rejection with high probability if not). Babai and Shlomo Moran formalized this framework in 1988, defining a hierarchy of complexity classes AM for protocols with k rounds starting with Arthur, and MA for those starting with Merlin, where AM = AM and MA = MA for constant rounds greater than or equal to 2, as additional rounds do not increase power beyond a constant. It remains an open question whether MA equals AM, though MA ⊆ AM is known. These classes capture languages verifiable via such interactions, with NP ⊆ MA ⊆ AM ⊆ Π₂ᵖ and AM ⊆ PSPACE. A key insight is that Arthur-Merlin protocols with polynomially many rounds equal the full class of interactive proofs IP, as shown by the equivalence between public-coin and private-coin models via simulations using pseudorandom generators or combinatorial arguments. Notable applications include placing graph non-isomorphism in AM, where Arthur sends a random permutation of one graph, and Merlin identifies the original graph to statistically confirm non-isomorphism with high probability if the graphs differ, highlighting the model's utility for intermediate problems between P and NP-complete ones. The framework has influenced subsequent developments in zero-knowledge proofs, derandomization, and quantum analogs like QMA.

Fundamentals

Interactive Proof Systems

An (IP) is a two-party protocol modeled as a game between a computationally bounded verifier, often denoted as , who runs in probabilistic time, and an unbounded prover, denoted as , who possesses unlimited computational power. The interaction proceeds over a number of rounds, during which the parties exchange messages, allowing the prover to convince the verifier of the truth of a statement in a L⊆{0,1}∗L \subseteq \{0,1\}^* based on a common input xx. The verifier's goal is to accept if x∈Lx \in L (a "yes-instance") and reject if x∉Lx \notin L (a "no-instance"), with the protocol's relying on probabilistic guarantees rather than deterministic . The protocol satisfies completeness: for every yes-instance x∈Lx \in L, there exists a prover strategy such that the verifier accepts with probability at least 2/32/3 over its random coins. Conversely, it ensures : for every no-instance x∉Lx \notin L, no prover strategy (even a malicious one) can make the verifier accept with probability greater than 1/31/3. These error probabilities can be reduced arbitrarily by repetition, and the constants 2/32/3 and 1/31/3 are conventional thresholds that capture the essential asymmetry in power between the parties. Interactive proof systems were introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985, originally in the context of zero-knowledge proofs, extending earlier notions of proof verification to interactive settings and laying the foundation for complexity classes like IP. A classic example is the graph non-isomorphism problem, where the input consists of two graphs G0G_0 and G1G_1 on nn vertices, and the prover aims to convince the verifier that G0G_0 and G1G_1 are not isomorphic. The verifier selects a random bit b∈{0,1}b \in \{0,1\}, applies a random permutation π\pi to GbG_b, and sends the resulting graph H=π(Gb)H = \pi(G_b) to the prover, who responds with the bit b′b' indicating which original graph was permuted; the verifier accepts if b′=bb' = b. If the graphs are non-isomorphic, the prover can always respond correctly by checking isomorphism against both G0G_0 and G1G_1, ensuring completeness; soundness holds because if the graphs are isomorphic, the prover has only a 1/21/2 chance of guessing bb correctly per round, and repetition amplifies the error. This protocol demonstrates how interaction enables proofs for problems outside NP without revealing additional information.

Public-Coin Protocols

In public-coin interactive proof systems, the verifier's messages consist solely of , known as coin tosses, which are publicly visible to the prover. This model contrasts with private-coin protocols, where the verifier's randomness is concealed within computationally generated messages that may depend on prior prover responses, potentially allowing for more succinct or powerful interactions but complicating theoretical analysis. A seminal result by and Sipser demonstrates that any private-coin interactive proof can be efficiently simulated by a public-coin protocol with only a constant increase in the number of rounds, while preserving the completeness and parameters. This simulation theorem implies that public-coin protocols are as expressive as their private-coin counterparts for defining the class of languages with interactive proofs, thereby establishing the sufficiency of public coins for most applications in complexity theory. The public-coin model simplifies the study of interactive proofs by making the verifier's behavior fully transparent and random, which facilitates proofs of containment within complexity classes and enables the development of the Arthur-Merlin paradigm, where the verifier (Arthur) issues random challenges and the prover (Merlin) responds accordingly. Some public-coin protocols achieve perfect completeness, meaning that for yes-instances, the verifier accepts with probability exactly 1, enhancing their utility in settings requiring deterministic acceptance on valid inputs.

MA Protocol

Formal Definition

The Merlin–Arthur (MA) protocol is a one-message in which the prover () sends a proof z∈{0,1}q(n)z \in \{0,1\}^{q(n)} to the verifier (), who then generates private random bits r∈{0,1}p(n)r \in \{0,1\}^{p(n)} (where p(n)p(n) and q(n)q(n) are polynomials in the input length nn) and decides acceptance using a probabilistic polynomial-time verifier V(x,z,r)V(x, z, r) that outputs 1 (accept) or 0 (reject). Unlike AM protocols, where randomness is public and sent to Merlin, in MA the verifier's random bits rr are private and used only for internal verification. This structure was originally formulated by Babai in as a framework related to nondeterministic verification with probabilistic checking. A language LL belongs to the complexity class MA (equivalently, MA, denoting the constant-round variant with Merlin starting) if there exist polynomials pp and qq, and verifier VV such that:
  • Completeness: For every x∈Lx \in L, there exists z∈{0,1}q(∣x∣)z \in \{0,1\}^{q(|x|)} such that Pr⁡r∼{0,1}p(∣x∣)[V(x,z,r)=1]≥23,\Pr_{r \sim \{0,1\}^{p(|x|)}} \left[ V(x, z, r) = 1 \right] \geq \frac{2}{3}, where the probability is over Arthur's uniform random choice of private bits rr, and the existential quantifier holds via an unbounded prover strategy.
  • Soundness: For every x∉Lx \notin L and every proof z∈{0,1}q(∣x∣)z \in \{0,1\}^{q(|x|)} (from any prover strategy), Pr⁡r∼{0,1}p(∣x∣)[V(x,z,r)=1]≤13.\Pr_{r \sim \{0,1\}^{p(|x|)}} \left[ V(x, z, r) = 1 \right] \leq \frac{1}{3}.
The acceptance probability in an MA protocol is thus formally Pr⁡[accept]=Pr⁡r[V(x,z,r)=1],\Pr[\text{accept}] = \Pr_r \left[ V(x, z, r) = 1 \right], reflecting the non-adaptive nature where Merlin's proof cannot depend on Arthur's randomness. Error probabilities in MA protocols can be amplified through repetition, similar to the related AM variant (where Arthur sends a public challenge before Merlin's response), but the proof-first order and universal quantifier over proofs allow parallel repetition to exponentially reduce both completeness and errors while preserving the one-message structure.

Examples

The inclusion of NP in MA follows directly from the structure of nondeterministic verification. For any language L in NP, Merlin sends a polynomial-length witness π that certifies x ∈ L, and Arthur, upon receiving π, runs the deterministic polynomial-time verifier from the NP machine to check if π is valid for x; if it is, Arthur accepts, otherwise rejects. Although Arthur's randomness is not utilized in this protocol, the model permits it, allowing the acceptance probability to be exactly 1 for yes-instances and 0 for no-instances. Similarly, BPP is contained in MA, as Arthur can disregard any message from Merlin (or treat a dummy empty proof) and simply execute the bounded-error probabilistic polynomial-time algorithm for the BPP language using his own private random coins. This yields the standard two-sided error probabilities of at most 1/3 for incorrect decisions, which can be amplified to negligible error via repetition if needed. Graph isomorphism provides a concrete illustration of an MA protocol, as the problem lies in NP and thus inherits the inclusion. Given two graphs G and H on n vertices, if they are isomorphic, Merlin sends a permutation π of the vertices; Arthur verifies by applying π to G and checking if the resulting equals that of H, which takes O(n^2) time. For non-isomorphic graphs, no such π exists, so Arthur rejects any purported proof with probability 1. An MA variant leverages witnesses for related problems, though the core verification remains deterministic. For the NP-complete problem of 3-coloring a graph, an MA protocol uses deterministic verification: Merlin sends a purported 3-coloring c of the vertices; Arthur checks all edges to ensure no edge connects two vertices of the same color under c. If G is 3-colorable, a valid c ensures acceptance with probability 1; if not, Arthur rejects any invalid c with probability 1. While is not necessary here (as in the NP inclusion), the MA model allows probabilistic verification as demonstrated in the BPP example. Despite these inclusions, MA does not capture the full power of the related AM class, as there exists an oracle relative to which MA is a proper subset of AM. This relativized separation, constructed using diagonalization techniques, highlights fundamental differences in the interactive capabilities between single-message - protocols and two-message - ones.

AM Protocol

Formal Definition

The – (AM) protocol is a two-message public-coin interactive proof system in which the verifier () initiates communication by sending a random challenge string y∈{0,1}p(n)y \in \{0,1\}^{p(n)} to the prover (), where p(n)p(n) is a polynomial in the input length nn; then responds with a proof string zz, and decides acceptance using a polynomial-time deterministic verifier V(x,y,z)V(x, y, z) that outputs 1 if the input xx, challenge yy, and proof zz are accepted. This structure was originally formulated by Babai in as a framework where responds to 's random "questions" in the form of coin tosses represented by yy. A language LL belongs to the complexity class AM (equivalently, AM, denoting the constant-round two-message variant) if there exist a pp and verifier VV such that:
  • Completeness: For every x∈Lx \in L, Pr⁡y∼{0,1}p(∣x∣)[∃z:V(x,y,z)=1]≥23,\Pr_{y \sim \{0,1\}^{p(|x|)}} \left[ \exists z : V(x, y, z) = 1 \right] \geq \frac{2}{3}, where the probability is over Arthur's uniform random choice of yy, and there exists an unbounded prover strategy ensuring the existential quantifier holds for a sufficient fraction of challenges.
  • Soundness: For every x∉Lx \notin L and every (possibly malicious) prover strategy π\pi mapping challenges to proofs (i.e., π:{0,1}p(∣x∣)→{0,1}q(∣x∣)\pi: \{0,1\}^{p(|x|)} \to \{0,1\}^{q(|x|)} for some qq), Pr⁡y∼{0,1}p(∣x∣)[V(x,y,π(y))=1]≤13.\Pr_{y \sim \{0,1\}^{p(|x|)}} \left[ V(x, y, \pi(y)) = 1 \right] \leq \frac{1}{3}.
The acceptance probability in an AM protocol is thus formally Pr⁡[accept]=Pr⁡y[∃z:V(x,y,z)=1],\Pr[\text{accept}] = \Pr_y \left[ \exists z : V(x, y, z) = 1 \right], reflecting the public-coin nature where Merlin's proof can adapt to the observed randomness. Error probabilities in AM protocols can be amplified through repetition, similar to the one-message MA variant (where Merlin sends the proof before Arthur's challenge), but the challenge-first order and per-challenge existential quantifier over proofs necessitate careful parallel repetition to exponentially reduce both completeness and soundness errors while preserving the two-message structure.

Relation to MA

The Arthur–Merlin (AM) protocol extends the Merlin–Arthur (MA) protocol by allowing the verifier (Arthur) to send a public random string before receiving the prover's (Merlin's) message, enabling Merlin to adapt the proof based on the randomness. This added interactivity makes AM strictly more powerful than MA in certain settings. To demonstrate the inclusion MA ⊆ AM, consider an MA protocol for a language L with perfect completeness and soundness at most 1/2. In the corresponding AM protocol, Arthur generates and sends a dummy random string y of polynomial length, which Merlin ignores and responds with the fixed MA proof π that accepts with probability 1 for all internal randomness r if x ∈ L. The verifier then discards y, independently samples its own random string r, and runs the MA verifier on (x, π, r). For completeness, acceptance occurs with probability 1 over r (and y is irrelevant). For soundness, regardless of how Merlin chooses π (possibly depending on y), the acceptance probability over r is at most 1/2 by the MA soundness condition, so the overall probability over y and r is at most 1/2. This simulation preserves the error probabilities up to constant factors via padding the input or random string lengths if needed. Although MA ⊆ AM holds unconditionally, the converse does not, and AM properly contains MA relative to certain oracles. Specifically, there exist oracles A such that MA^A ⊊ AM^A, establishing that the inclusion is proper in the relativized world. These oracle separations, dating back to results in the 1980s, highlight the additional power of public randomness in AM, as Merlin can condition the proof on Arthur's message in ways not possible in MA. A canonical example illustrating AM's greater expressive power is the graph non-isomorphism problem (GNI), which lies in AM but is not known to be in MA. GNI consists of pairs of n-vertex graphs (G_0, G_1) promised to be non-isomorphic, where the goal is to verify the promise. The AM protocol proceeds as follows: Arthur selects a random bit b ∈ {0,1} and a π of the vertex set , computes the relabeled graph π(G_b) (by permuting the accordingly), and sends the of π(G_b) to Merlin. Merlin responds with a bit b' indicating which original graph (G_0 or G_1) the received matrix derives from. Arthur accepts if b' = b and rejects otherwise. For completeness, if G_0 ≇ G_1, then π(G_0) ≇ π(G_1) for any π, so an honest Merlin can always distinguish the received matrix and return the correct b', yielding acceptance probability 1. For , if G_0 ≅ G_1, then the distributions of π(G_0) and π(G_1) are identical (since isomorphisms preserve the action of permutations), so any Merlin guesses b correctly with probability at most 1/2; repeating the protocol O(log n) times in parallel reduces the soundness error to negligible. This protocol, introduced by Babai, demonstrates AM's ability to verify properties requiring adaptive proofs based on public randomness. The inclusion of GNI in AM has broader implications: AM captures promise problems like GNI, which belong to coNP but lack known MA protocols, suggesting AM's capacity to handle coNP-type verifications beyond NP via public-coin interaction. Goldwasser and Sipser showed that any private-coin interactive proof can be simulated by a public-coin protocol with a constant increase in the number of rounds. Babai and Moran established that for any constant k ≥ 2, AM = AM. This equivalence underscores AM's foundational role in interactive proof systems.

Advanced Variants

Multi-Round Protocols

Multi-round –Merlin protocols generalize the two-round AM protocol by allowing multiple alternations between 's random messages (public coins) and 's deterministic responses. The class AM is defined as the set of languages recognized by public-coin interactive protocols consisting of k messages, where k is odd and sends the first (and last) message, with 's messages being random strings and 's being proofs based on the input and prior messages. Note: Some sources, including the article introduction, reverse the starting player for AM and MA; here we follow Babai's original definition. This structure ensures the verifier () remains probabilistic polynomial-time while the prover () is computationally unbounded. The AM hierarchy, denoted AM for constant k and AM[poly] for polynomial k, was introduced by in the mid-1980s as part of his work on randomized proof systems for and related problems, progressing from the two-round AM case to protocols with polynomially many rounds to capture broader complexity classes. Babai showed that the hierarchy collapses for constant rounds, with AM = AM for any constant k ≥ 2, but multi-round variants extend the power significantly. The class AM[poly], featuring polynomially many rounds, is equivalent to the interactive proof class IP, which allows general (private-coin) interactive protocols with rounds; this equivalence holds because public coins can simulate private coins with only a linear increase in rounds. established in that IP = AM[poly] = , demonstrating that any language in admits a multi-round Arthur–Merlin protocol verifiable in time. Shamir's proof constructs an interactive protocol for quantified formulas (TQBF), the canonical problem, by arithmetizing the formula into a and using interactive techniques to verify its value. A key building block in Shamir's theorem and related results is the sumcheck protocol, a multi-round AM protocol introduced by Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan in 1992. The sumcheck protocol enables Arthur to verify whether the sum of a given multivariate polynomial pp of degree at most dd over the Boolean hypercube {0,1}d\{0,1\}^d equals a claimed value ss, through dd interactive rounds where Merlin provides univariate restrictions of pp and Arthur challenges with random points to reduce the problem dimension by one each time. This protocol has soundness error at most d⋅(d/∣F∣)=O(d2/∣F∣)d \cdot (d / |\mathbb{F}|) = O(d^2 / |\mathbb{F}|) when performed over a finite field F\mathbb{F} with ∣F∣>2d|\mathbb{F}| > 2d (to ensure the error is small, typically ∣F∣|\mathbb{F}| is chosen much larger, e.g., ∣F∣≥d3|\mathbb{F}| \geq d^3). It serves as a foundational tool for approximating #SAT—the problem of counting satisfying assignments—by arithmetizing the permanent or other counting functions and iteratively summing over variables. While AM[poly] fully captures , round reduction techniques show that fewer rounds suffice under certain conditions. Constant-round AM protocols are known to characterize assuming the existence of one-way functions or related , via black-box simulations and parallel repetition. Unconditionally, AM protocols with O(log⁡n)O(\log n) rounds equal IP, achieved through iterative applications of linear round speed-up arguments that halve the number of rounds while preserving polynomial-time verifiability and .

Quantum Variants

Quantum variants of Arthur–Merlin protocols adapt the classical framework to , where Merlin provides quantum proofs and Arthur performs quantum measurements to verify claims with high probability. The class QMA, the quantum analogue of MA, consists of decision problems where a quantum polynomial-time verifier Arthur accepts "yes" instances with probability at least 2/3 if Merlin supplies an accepting quantum proof state, and rejects "no" instances with probability at most 1/3 regardless of the proof; formally, for input xx of length nn, there exists a polynomial-time quantum verifier VV such that if x∈Lx \in L, there is a quantum state ∣ψ⟩|\psi\rangle on poly(nn) qubits where Pr⁡[V(x,∣ψ⟩) accepts]≥2/3\Pr[V(x, |\psi\rangle) \text{ accepts}] \geq 2/3, and if x∉Lx \notin L, for all ∣ψ⟩|\psi\rangle, Pr⁡[V(x,∣ψ⟩) accepts]≤1/3\Pr[V(x, |\psi\rangle) \text{ accepts}] \leq 1/3. This class was introduced by Kitaev in 1999. A related class is QAM (or quantum AM), which extends the public-coin model to quantum settings with two messages: Arthur sends classical random bits to Merlin, who responds with a quantum proof, and Arthur then verifies via quantum computation. QAM protocols maintain the completeness-soundness gap of the classical AM while incorporating in proofs and verification. It is known that QMA ⊆\subseteq QAM ⊆\subseteq QIP, where QIP denotes quantum interactive proofs with unrestricted quantum message exchanges; furthermore, QIP = . A representative example in QMA is quantum state certification, where Merlin prepares a purported quantum state ∣ψ⟩|\psi\rangle claimed to be close to a target state (e.g., a graph state or eigenvector of a Hamiltonian), and Arthur verifies by applying a polynomial-time (such as a unitary transformation) followed by measurements in the computational basis to check consistency with the promise. This captures problems like approximating the energy of local Hamiltonians, which is QMA-complete. In 2016, Vidick and Watrous provided a comprehensive survey on quantum proofs, establishing QMA-completeness for additional problems such as verifying entangled projection games and certain quantum instances, though significant open questions remain regarding separations and further completeness results post-2016. Since 2016, further QMA-complete problems have been identified, including certain quantum games and constraint systems (e.g., , 2017; surveys up to 2025), while oracle separations like QMA \not\subseteq QCMA under random highlight structural differences (Aaronson et al., ).

Complexity Properties

Class Inclusions

The Merlin-Arthur class MA contains NP, since any nondeterministic for a yes-instance in NP can be sent by to , who verifies it deterministically without . Similarly, coRP is contained in MA: for a coRP language, Merlin sends a purported witness that the input is a no-instance, and Arthur's randomized verification rejects with high probability only if the witness is invalid, leveraging the one-sided error of coRP. These inclusions position MA as a probabilistic extension of NP that incorporates verifier while maintaining . MA is strictly contained in AM relative to certain oracles. A relativizing proof constructs an oracle CC such that MAC≠AMC\mathsf{MA}^C \neq \mathsf{AM}^C, demonstrating that the order of 's nondeterministic message and 's random coins can lead to separations in relativized worlds. Unconditionally, MA ⊆\subseteq AM holds via the following simulation: sends the witness as in the MA protocol, sends his random bits publicly, sends a dummy message, and verifies as in the original MA protocol using the public bits. Furthermore, BPP ⊆\subseteq MA, as shown by amplifying the success probability of a BPP and using to certify low-error regions in the random string space, effectively derandomizing via nondeterminism. AM is contained in the polynomial hierarchy PH, specifically AM ⊆Σ2p\subseteq \Sigma_2^p, through Babai's 1985 result that interprets the AM protocol as an over Merlin's message followed by a over Arthur's coins, with the verifier's acceptance condition forming a polynomial-time predicate. This places AM within the second level of PH. Additionally, AM ⊆\subseteq IP ⊆\subseteq , since the public-coin two-message AM protocol extends naturally to the general interactive proof model IP, which equals PSPACE by Shamir's theorem via arithmetization techniques for quantified Boolean formulas. Relative to random oracles, AM may separate from PH, but unconditional equality remains open, as does whether AM equals NP or —a question unresolved since the introduction of these classes in the 1980s.

Complete Problems

Graph non-isomorphism, the promise problem of deciding whether two given graphs are non-isomorphic, resides in the complexity class AM but is not known to be in MA. In the canonical AM protocol for this problem, interact over two rounds to demonstrate the absence of an . Merlin commits to an between one of the input graphs GG and a random isomorphic copy G′G', while Arthur challenges Merlin to open the commitment on a random vertex or edge to verify consistency; if the graphs are isomorphic, Merlin succeeds with probability at most 1/21/2, but if non-isomorphic, Merlin can always succeed by choosing an appropriate invariant. This protocol, introduced in the context of zero-knowledge proofs, highlights the power of public randomness in AM over the private-witness model of MA. In contrast, the promise version of graph isomorphism—deciding whether two graphs are isomorphic given the promise that they either are or are not—lies in MA. Merlin simply provides a purported isomorphism as a witness, which Arthur verifies deterministically in polynomial time by checking that the mapping preserves adjacency for all edges. This places graph isomorphism in MA (and more precisely in NP), but its complement requires the interactive structure of AM. MA-complete problems illustrate the expressive power of the class through natural combinatorial promise problems. One such problem is the Approximately-Clean Approximate-Connected-Component (ACAC), where, given a succinctly represented graph with marked vertices and parameters ϵ,δ>0\epsilon, \delta > 0, one decides whether there exists a connected component consisting entirely of unmarked vertices or whether every δ\delta-approximate connected component contains at least an ϵ\epsilon-fraction of marked vertices. ACAC is in MA via a verification protocol using random walks to sample components, and it is MA-hard by reduction from the Set-Constraint Satisfaction Problem (SetCSP). SetCSP generalizes constraint satisfaction by allowing constraints over sets of strings rather than single assignments; given a set SS of strings and set-constraints, decide if SS satisfies all constraints or is ϵ\epsilon-far from any satisfying set under Hamming distance. SetCSP is MA-complete, with membership shown via reduction to ACAC and hardness from the universal MA verification problem. Another MA-complete problem arises in quantum-inspired settings: the Local Hamiltonian Problem with succinct ground state (promise version). Here, given a local Hamiltonian HH on nn qubits and promise gaps a<ba < b, decide if the ground state energy λmin⁡(H)≤a\lambda_{\min}(H) \leq a or ≥b\geq b, with the additional promise that in the yes case, the ground state ∣ψ⟩|\psi\rangle is succinctly representable by a polynomial-size classical circuit. This is in MA because Merlin provides the circuit description, and Arthur uses randomized classical sampling (via simulation with a ) to estimate the energy with high probability. Hardness follows from encoding arbitrary MA instances into Hamiltonians where the succinct ground state corresponds to a valid . While the standard Local Hamiltonian without succinctness is QMA-complete, this variant underscores MA's role in verifiable quantum ground states under classical succinctness assumptions. AM protocols demonstrate hardness for certain quantified variants, such as problems involving alternating existential and universal quantifiers over formulas, which capture the interactive quantification in AM. These variants are AM-hard under polynomial-time reductions, as they simulate the two-message structure where Merlin provides an existential and Arthur's enforces universal checks. More broadly, AM relates to probabilistically checkable proofs (PCPs) via a PCP characterization: a 2-round constraint-satisfaction problem is complete for the version of AM, analogous to the PCP theorem's characterization of NP. This connection shows that AM protocols can verify PCPs for NP problems with constant query complexity and , amplifying the class's power for interactive verification. A key application of AM protocols lies in approximating functions in #P, the class of counting problems. The sumcheck protocol enables an AM proof system where Merlin convinces that the sum of a low-degree multivariate over a equals a claimed value, with Arthur's random challenges reducing the sum to univariate evaluations. This protocol, run in multiple rounds, approximates #SAT (counting satisfying assignments) within a multiplicative factor, placing approximate #P in AM under interactive access. The verifier uses O(log⁡n)O(\log n) randomness and communication, highlighting AM's efficiency for counting beyond deterministic verification.

Recent Developments

Fine-Grained Applications

In fine-grained complexity theory, recent advancements have leveraged Merlin-Arthur (MA) protocols to establish improved verification procedures for central problems, providing tighter connections between probabilistic verification and deterministic computation under standard hardness assumptions. A seminal contribution is the development of MA protocols achieving near-optimal running times for problems like the Orthogonal Vectors (OV) problem, where detecting an orthogonal pair among n vectors in d dimensions (with d = ω(log n)) can be verified in Õ(n d) time, surpassing previous nondeterministic bounds and aligning with the quadratic baseline under the OV conjecture. For graph-theoretic problems, MA protocols have enabled subquadratic verification for all-pairs shortest paths (APSP), where the entire n × n can be certified in Õ(n²) total time, optimal given the output size, but with Arthur's verification step avoiding the full O(n^3) overhead through Merlin's succinct proof of intermediate distances. This improves upon earlier nondeterministic approaches requiring Õ(n^{2.94}) time and highlights MA's utility in batch-verifying computations. In the context of , an observation establishes that no algebrizing MA protocol exists for k-SAT (or equivalently, k-UNSAT) running in time below 2^{n/2} / n^{ω(1)}, distinguishing algebraic proof techniques from non-algebrizing ones needed for subexponential verification of k-UNSAT in 2^{n(1/2 - δ/k)} · poly(n, m) time. Extending these to Arthur-Merlin (AM) protocols, instance-wise hardness results from 2025 reveal near-equivalences between nondeterministic refutation and derandomization, showing that derandomizing AM protocols on hard instances implies efficient refuters for AM-complete languages, analogous to BPP but adapted to interactive settings with public randomness. These equivalences tighten bounds on the power of AM versus MA in fine-grained regimes, suggesting potential separations under assumptions like the (), where AM may not collapse to MA for problems requiring multiple rounds or private coins. Overall, such results, building on ITCS innovations, underscore MA/AM's role in bridging fine-grained hardness conjectures with practical verification efficiency.

Other Models

The Arthur–Merlin protocol has been extended to the , where the input arrives as a sequential that Arthur processes in a single pass while maintaining limited . In this framework, termed Arthur-Merlin streaming complexity, Merlin provides an initial proof or annotation to Arthur before the begins, enabling verification of properties that would otherwise require substantial in classical randomized streaming algorithms. Foundational work by Chakrabarti, Cormode, McGregor, Thaler, and Venkataraman established verifiable computation protocols using Arthur-Merlin communication, demonstrating that one or two rounds of interaction suffice for solving query problems like estimating the number of distinct elements in a . A canonical Arthur-Merlin streaming algorithm, developed by Gur and Raz, applies to a range of streaming problems, including those related to identity testing (verifying if a stream matches a known distribution) and closeness testing (comparing two empirical distributions from streams). In this protocol, Merlin sends compact sketches, such as evaluations of polynomials over finite fields that encode the stream's statistical properties, with proof length O~(w)\tilde{O}(w) for a parameter ww. Arthur then streams the input, using O~(s)\tilde{O}(s) space to generate random evaluation points ξ\xi and verify if the stream's partial computations match Merlin's sketches at those points; mismatch leads to rejection with high probability. For instance, in the Distinct Elements problem—which underpins support size estimation for identity testing—the algorithm achieves an optimal tradeoff where s⋅w=Ω(n)s \cdot w = \Omega(n) for universe size nn, allowing Arthur to use polylogarithmic space when Merlin provides a longer proof. These protocols demonstrate that Arthur-Merlin streaming captures greater expressive power than classical streaming BPP, solving problems like frequency moments estimation in O(log⁡n)O(\log n) space that require Ω(n)\Omega(n) space in BPP alone. In quantum settings, Arthur-Merlin protocols have evolved to address state synthesis and verification tasks beyond classical streams. A 2025 development by Delavenne, Le Gall, , and Miyamoto introduced stateQMA, a variant of quantum Merlin- where Merlin prepares a as proof, and verifies whether it enables efficient synthesis of target states for problems like synthesis. This fills post-2016 gaps in QMA variants for , where protocols now support efficient reconstruction and verification of high-dimensional states using shadow techniques integrated into Merlin- frameworks. For example, verifying a uniform superposition state ∣ψ⟩=12n∑x∈{0,1}n∣x⟩|\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle
Add your contribution
Related Hubs
User Avatar
No comments yet.