Arthur–Merlin protocol

In computational complexity theory, an ArthurMerlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too). This notion was introduced by Babai (1985). Goldwasser & Sipser (1986) proved that all 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); but 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 23 of the time, and if whenever the answer is "no", Arthur will never accept more than 13 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

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. However, Arthur is not necessarily a BPP verifier as it is not known whether MA is contained in the class  \exists BPP.[1]

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|,

The second condition can alternatively be written as

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

The complexity class AM (or AM[2]) is the set of decision problems that can be decided in polynomial time by an ArthurMerlin 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|,

The second condition here can be rewritten as

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 before deciding his answer.

Properties

Footnotes

  1. https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#existsbpp
  2. For a proof, see Rafael Pass and Jean-Baptiste Jeannin (March 24, 2009). "Lecture 17: Arthur-Merlin games, Zero-knowledge proofs" (PDF). Retrieved June 23, 2010.
  3. Symmetric Alternation captures BPP
  4. Madhu Sudan, Algebra and Computation lecture notes , lecture 22

References

External links

This article is issued from Wikipedia - version of the Sunday, March 13, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.