词条 | 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 {{Harvtxt|Babai|1985}}. {{Harvtxt|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); 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 {{frac|2|3}} of the time, and if whenever the answer is "no", Arthur will never accept more than {{frac|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. MAThe 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|,
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. AMThe 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|,
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
Footnotes1. ^For a proof, see {{cite web|url=http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture17.pdf|title=Lecture 17: Arthur-Merlin games, Zero-knowledge proofs|author=Rafael Pass and Jean-Baptiste Jeannin|date=March 24, 2009|accessdate=June 23, 2010}} 2. ^{{Cite paper |last=Impagliazzo |first=Russell |last2=Wigderson |first2=Avi |date=1997-05-04 |title=P = BPP if E requires exponential circuits: derandomizing the XOR lemma |url=http://dl.acm.org/citation.cfm?id=258533.258590 |publisher=ACM |pages=220–229 |doi=10.1145/258533.258590 |isbn=0897918886}} 3. ^{{cite web|url=http://www.ccs.neu.edu/home/koods/papers/russell98symmetric.pdf |format=PDF|title=Symmetric Alternation captures BPP|website=Ccs.neu.edu|accessdate=2016-07-26}} 4. ^{{Cite journal|last=Vereschchagin|first=N.K.|title=On the power of PP|url=http://ieeexplore.ieee.org/document/215389/|journal=[1992] Proceedings of the Seventh Annual Structure in Complexity Theory Conference|language=en-US|publisher=IEEE Comput. Soc. Press|doi=10.1109/sct.1992.215389|isbn=081862955X}} 5. ^{{Cite paper |last=Vidick |first=Thomas |last2=Watrous |first2=John |date=2016 |title=Quantum Proofs |url=http://mr.crossref.org/iPage?doi=10.1561%2F0400000068 |journal=Foundations and Trends® in Theoretical Computer Science |volume=11 |issue=1-2 |pages=1–215 |doi=10.1561/0400000068 |issn=1551-305X}} 6. ^{{cite web|url=http://people.csail.mit.edu/madhu/FT98/course.html |title=Course: Algebra and Computation |website=People.csail.mit.edu |date= |accessdate=2016-07-26}} References
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora | last2=Barak | first2=Boaz | title=Computational Complexity: A Modern Approach | url = http://www.cs.princeton.edu/theory/complexity/ | publisher=Cambridge | year=2009 | isbn=978-0-521-42426-4 }}.
External links
1 : Randomized algorithms |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。