Information about Ma (complexity)
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 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
..... Click the link for more information.
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 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
As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g.
..... Click the link for more information.
..... Click the link for more information.
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 ascertain whether a given string
..... Click the link for more information.
..... Click the link for more information.
László Babai (called Laci by friends and colleagues), born in 1950, is a professor of mathematics and computer science at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the
..... Click the link for more information.
..... Click the link for more information.
Shafrira Goldwasser
Shafrira Goldwasser
Born 1958
Field Computer Science, Cryptography
Institutions Massachusetts Institute of Technology,
Weizmann Institute of Science
..... Click the link for more information.
Shafrira Goldwasser
Born 1958
Field Computer Science, Cryptography
Institutions Massachusetts Institute of Technology,
Weizmann Institute of Science
..... Click the link for more information.
Michael Sipser is a professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. His research area is complexity theory.
..... Click the link for more information.
..... Click the link for more information.
..... Click the link for more information.
oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class.
..... Click the link for more information.
..... Click the link for more information.
BPP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/3 for all instances. The abbreviation BPP refers to Bounded-error, Probabilistic, Polynomial time.
..... Click the link for more information.
..... Click the link for more information.
In computational complexity theory, a complexity class is a set of problems of related complexity. A typical complexity class has a definition of the form:
..... Click the link for more information.
- the set of problems that can be solved by abstract machine M using O(f(n)) of resource R (n
..... Click the link for more information.
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem.
..... Click the link for more information.
..... Click the link for more information.
In computational complexity theory, NP ("Non-deterministic Polynomial time") is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine.
..... Click the link for more information.
..... Click the link for more information.
BPP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/3 for all instances. The abbreviation BPP refers to Bounded-error, Probabilistic, Polynomial time.
..... Click the link for more information.
..... Click the link for more information.
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.
..... Click the link for more information.
Definitions
There are multiple equivalent definitions of the classes of the polynomial hierarchy...... Click the link for more information.
Advice is a concept in complexity theory.
An advice string is an extra input to a Turing machine which is allowed to depend on the length n of the input, but not on input itself.
..... Click the link for more information.
An advice string is an extra input to a Turing machine which is allowed to depend on the length n of the input, but not on input itself.
..... Click the link for more information.
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.
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
