| Arthur-merlin Protocol |
Shopping Protocol |
Website Links For Protocol |
Information AboutArthur-merlin Protocol |
| CATEGORIES ABOUT ARTHUR-MERLIN PROTOCOL | |
| computational complexity theory | |
|
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 is the set of Decision Problem s 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, the class '''AM is equal to '''AM[1 '''. 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 immmediate, 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 with 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: Madhu Sudan's MIT course on advanced complexity |
|
|