Arthur-Merlin protocol

Arthur-Merlin protocol

In computational complexity theory, an Arthur-Merlin 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 et al. They proved that all languages with constant-length interactive proofs with private coins also have interactive proofs with public coins. Later, Goldwasser and Sipser generalized this result to proofs of arbitrary length.

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 decidable 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 BPP verifier, assuming it is allotted polynomial time to make its decisions and queries.

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 where there is only one query/response pair. The complexity class AM [k] is the set of problems that can be decided in polynomial time, with k queries and responses.

The complexity class MA is the set of decision problems that can be decided in polynomial time with (unlimited) communication only from Merlin to Arthur.

For any fixed k>=2, the class AM [k] is equal to AM [2] . It is open whether AM and MA are different. Moreover 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. MA is contained in AM, since Arthur need only send a void "query" at the start, to which Merlin will respond with the information it needs to send under the MA protocol. 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. MA is also contained in NP/poly, the class of decision problems computable in non-deterministic polynomial time with a polynomial size advice.

See also: IP for a class with more than a constant number of interactions.

Reference: [http://theory.lcs.mit.edu/~madhu/ST05/ Madhu Sudan's MIT course on advanced complexity]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Arthur–Merlin protocol — In computational complexity theory, an Arthur–Merlin 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… …   Wikipedia

  • Interactive proof system — In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to… …   Wikipedia

  • IP (complexity) — In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Goldwasser, et al. in 1985. An interactive proof system consists …   Wikipedia

  • NP (complexity) — Diagram of complexity classes provided that P ≠ NP. The existence of problems outside both P and NP complete in this case was established by Ladner.[1] In computational complexity theory, NP is one of the most fundamental complexity classes. The… …   Wikipedia

  • Liste von Komplexitätsklassen — Dies ist eine Liste von Komplexitätsklassen, die in der Komplexitätstheorie betrachtet werden. Die Klassen verwenden in ihren Definitionen verschiedene Maschinenmodelle. Die wichtigsten Modelle sind Turingmaschinen; diese können deterministisch,… …   Deutsch Wikipedia

  • AM — AM, Am, or am may refer to: * Master of Arts (postgraduate), ( Artium Magister ) alternative abbreviation for a Master s degree in Arts * Americium, a chemical element with symbol Am * Arthur Merlin protocol, an interactive proof system in… …   Wikipedia

  • AI-complete — In the field of artificial intelligence, the most difficult problems are informally known as AI complete or AI hard, implying that the difficulty of these computational problems is equivalent to solving the central artificial intelligence problem …   Wikipedia

  • MA — is an abbreviation and Ma may be either an abbreviation or a word, each of which may refer to:in academia: *Master of Arts (postgraduate) (MA), academic degree *Master of Arts (Oxbridge and Dublin) (MA), degree given by universities of Oxford,… …   Wikipedia

  • List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… …   Wikipedia

  • Alice and Bob — The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, Alice sends a message to Bob encrypted with his public key is… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”