The class of decision problems solvable by a Merlin-Arthur protocol, which goes as follows. Merlin, who has unbounded computational resources, sends Arthur a polynomial-size purported proof that the answer to the problem is "yes." Arthur must verify the proof in BPP (i.e. probabilistic polynomial-time), so that
- If the answer is "yes," then there exists a proof such that Arthur accepts with probability at least 2/3.
- If the answer is "no," then for all proofs Arthur accepts with probability at most 1/3.
An alternative definition requires that if the answer is "yes," then there exists a proof such that Arthur accepts with certainty. However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).
Shown in [San07] that MA/1 does not have circuits of size for any . In the same paper, the result was used to show that MA/1 cannot be solved on more than a fraction of inputs having length by any circuit of size . Finally, it was shown that MA does not have arithmetic circuits of size .
MAcc: Communication Complexity MA
Here, Alice and Bob collectively constitute "Arthur", and the cost of an MAcc communication protocol is defined as the bit length of Merlin's message plus the communication cost of the ensuing randomized protocol between Alice and Bob. (Not charging for the length of Merlin's message would enable every function to be computed with constant cost in this model.)
It is open to prove that there exists an explicit two-party function whose MAcc-type communication complexity is ω(n1/2).
MA': Sparse MA
The subclass of MA such that for each input size n, there is a sparse set Sn that Merlin's proof string always belongs to (no matter what the input is).
MAC0: Majority of AC0
Same as AC0, except now we're allowed a single unbounded-fanin majority gate at the root.
Defined in [JKS02].
MAE: Exponential-Time MA With Linear Exponent
MAEXP: Exponential-Time MA
There is a problem in MAEXP that does not have polynomial-size circuits [BFT98]. On the other hand, there is an oracle relative to which every problem in MAEXP does have polynomial-size circuits.
[MVW99] considered the best circuit lower bound obtainable for a problem in MAEXP, using current techniques. They found that this bound is half-exponential: i.e. a function f such that f(f(n))=2n. Such functions exist, but are not expressible using standard asymptotic notation.
mAL: Monotone AL
MAPOLYLOG: MA With Polylog Verifier
Identical to MA except for that Arthur (the verifier) has random access to the proof string given by Merlin, and is limited to running times of order .
MaxNP: Maximization NP
MaxPB: MaxNP Polynomially Bounded
The subclass of MaxNP problems for which the cost function is guaranteed always to be bounded by a polynomial.
MinPB can be defined similarly.
Defined in [KT94].
MaxSNP: Maximization SNP
Defined in [PY88], where the following was also shown:
- Max3SAT is MaxSNP-complete. (Max3SAT is the problem of finding an assignment that maximizes the number of satisfied clauses in a CNF formula with at most 3 literals per clause.)
- Any problem in MaxSNP can be approximated to within a fixed ratio.
MaxSNP0: Generating Class of MaxSNP
The class of function problems expressible as "find a relation such that the set of k-tuples for which a given SNP predicate holds has maximum cardinality."
For example (see [Pap94]), the Max-Cut problem can be expressed as follows:
- Given a graph G, find a subset S of vertices that maximizes the number of pairs (u,v) of vertices such that u is in S, and v is not in S, and G has an edge from u to v.
Defined in [PY88].
mcoNL: Complement of mNL
See also: mL.
MinPB: MinNP Polynomially Bounded
Same as MaxPB but for minimization instead of maximization problems.
MIP: Multi-Prover Interactive Proof
Same as IP, except that now the verifier can exchange messages with many provers, not just one. The provers cannot communicate with each other during the execution of the protocol, so the verifier can "cross-check" their assertions (as with suspects in separate interrogation rooms).
Defined in [BGK+88].
Let MIP[k] be the class of decision problems for which a "yes" answer can be verified with k provers. Then for all k>2, MIP[k] = MIP = MIP [BGK+88].
MIP*: MIP With Quantum Provers
Same as MIP, except that the provers can share arbitrarily many entangled qubits. The verifier is classical, as are all messages between the provers and verifier.
Even MIP*[4,poly] and MIP[5,1] contain NEXP [IV12].
MIP*[2,1] contains XOR-MIP*[2,1].
MIPns: MIP with Non-Signaling Provers
Same as MIP, except that the provers can have non-signaling strategies.
MIPEXP: Exponential-Time Multi-Prover Interactive Proof
The exponential-time analogue of MIP.
In the unrelativized world, equals NEEXP.
(Mk)P: Acceptance Mechanism by Monoid Mk
A monoid is a set with an associative operation and an identity element (so it's like a group, except that it need not have inverses).
Then (Mk)P is the class of decision problems solvable by an NP machine with the following acceptance mechanism. The ith computation path (under some lexicographic ordering) outputs an element mi of Mk. Then the machine accepts if and only if m1m2...ms is the identity (where s is the number of paths).
Defined by Hertrampf [Her97], who also showed the following (in the special case M is a group):
- If G is any nonsolvable group (for example S5, the symmetric group on 5 elements), then (G)P = PSPACE.
- (Zk)P = coModkP, where Zk is the cyclic group on k elements.
- If |G|=k, then (G)P contains coModkP.
mL: Monotone L
The class of decision problems solvable by a family of monotone log-width polynomial-size leveled circuits. (A leveled circuit is one where gates on each level can depend only on the level immediately below it.)
Defined in [GS90], who raise as an open problem to define a uniform version of mL.
MM: Problems reducible to matrix multiplication
The set of all problems reducible to matrix multiplication. That is, the set of problems that can be reduced to the multiplication of two square matrices can be reduced to in linear time.
Currently, the best known algorithm for multiplying two matrices is the Coppersmith–Winograd_algorithm, which has a time complexity of [CW90]. Note that for the general problem, a lower bound of is trivial from the number of elements being considered.
MMSNP: Monadic Monotone SNP
- The second order existentially quantified variables, known as the proof relations, are restricted to be monadic. (Monadic relations can be treated as sets.)
- Any relations in the formula other than the proof relations must occur only negated (the formula is monotone).
- No inequality relations can occur in the formula.
MMSNP seems to obey dichotomy, by excluding languages that are NP-intermediate. This is still open but widely believed. Dropping any of the restrictions monotone/monadic/without inequalities allows NP-intermediate languages unless P = NP, since any problem in NP is polynomial time equivalent to a problem in each of these broader classes. MMSNP therefore seems to be a maximal fragment of NP where NP-intermediate languages are excluded.
Every constraint satisfaction problem with a fixed target structure is expressible in MMSNP, and there is a polynomial time Turing reduction from every MMSNP query to finitely many constraint satisfaction problems. MMSNP therefore seems to capture the class of constraint satisfaction problems with fixed templates, CSP.
mNC1: Monotone NC1
The class of decision problems solvable by a family of monotone NC1 circuits (i.e. AND and OR gates only).
A uniformity condition could also be imposed.
Defined in [GS90].
mNL: Monotone NL
mNL is the class of decision problems solvable by a monotone nondeterministic log-space Turing machine.
See also: mL.
mNP: Monotone NP
The class of decision problems for which a 'yes' answer can be verified in mP (that is, monotone polynomial-time). The monotonicity requirement applies only to the input bits, not to the bits that are guessed nondeterministically. So, in the corresponding circuit, one can have NOT gates so long as they depend only on the nondeterministic guess bits.
ModkL: Mod-k L
For any prime k, ModkLModkL = ModkL [HRV00].
A language if there are functions and such that for all strings :
- There exists a prime and a natural number such that .
- if and only if .
Defined in [AV04].
ModkP: Mod-k Polynomial-Time
For any k>1: The class of decision problems solvable by an NP machine such that the number of accepting paths is divisible by k, if and only if the answer is "no."
Mod2P is more commonly known as ⊕P "parity-P."
[Her90] and [BG92] showed that ModkP is the set of unions of languages in ModpP for each prime p that divides k. In particular, if p is prime, then ModpP = Modp^mP for all positive integers m. A further fact is that ModpP is closed under union, intersection, and complement for p prime.
On the other hand, if k is not a prime power, then there exists an oracle relative to which ModkP is not closed under intersection or complement [BBR94].
ModP: ModkP With Arbitrary k
The class of decision problems solvable by a ModkP machine where k can vary depending on the input. The only requirement is that 0k be computable in polynomial time.
ModZkL: Restricted ModkL
The class of decision problems solvable by a nondeterministic logspace Turing machine, such that
- If the answer is "yes," then the number of accepting paths is not congruent to 0 mod k.
- If the answer is "no," then there are no accepting paths.
mP: Monotone P
The definition of this class, due to [GS90], is not obvious. First, a monotone nondeterministic Turing machine is one such that, whenever it can make a transition with a 0 on its input tape, it can also make that same transition with a 1 on its input tape. (This restriction does not apply to the work tape.) A monotone alternating Turing machine is subject to the restriction that it can only reference an input bit x by, "there exists a z at most x," or "for all z at least x."
Actually there's a caveat: A monotone Turing machine or circuit can first negate the entire input, then perform a monotone computation. That way it becomes meaningful to talk about whether a monotone complexity class is closed under complement.
Deciding whether a bipartite graph has a perfect matching, despite being both a monotone problem and in P, requires monotone circuits of superpolynomial size [Raz85b]. Letting MONO be the class of monotone problems, it follows that mP is strictly contained in MONO ∩ P.
MP: Middle-Bit P
The class of decision problems such that for some #P function f, the answer on input x is 'yes' if and only if the middle bit of f(x) is 1.
Defined in [GKR+95].
MPC: Monotone Planar Circuits
The class of decision problems solvable by a family of monotone stratified planar circuits (a uniformity condition may also be imposed).
Such a circuit can contain only AND and OR gates of bounded fanin. It must be embeddable in the plane with no wires crossing. Furthermore, the input bits can only be accessed at the bottom level, where they are listed in order (x1,...,xn).
Defined in [DC89].
[BLM+99] showed that we can assume without loss of generality that the circuit has width n and depth n3.
mP/poly: Monotone P/poly
The class of decision problems solvable by a nonuniform family of polynomial-size Boolean circuits with only AND and OR gates, no NOT gates. (Or rather, following the definitions of [GS90], the entire input can be negated as long as there are no other negations.)
More straightforward to define than mP.
mTC0: Monotone TC0
The class of decision problems solvable by a family of monotone TC0 circuits (i.e. constant-depth, polynomial-size, AND, OR, and threshold gates, but no NOT gates).
A uniformity condition could also be imposed.
Defined in [GS90].