Complexity Zoo:M

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

---

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

---

MA - MA^cc - MA' - MAC⁰ - MA_E - MA_EXP - mAL - MA_POLYLOG - MaxNP - MaxPB - MaxSNP - MaxSNP₀ - mcoNL - MinPB - MIP - MIP* - MIP^ns - MIP_EXP - (M_k)P - mL - MM - MMSNP - mNC¹ - mNL - mNP - Mod_kL - ModL - Mod_kP - ModP - ModPH - ModZ_kL - mP - MP - MPC - mP/poly - mTC⁰

MA: Merlin-Arthur

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

1. If the answer is "yes," then there exists a proof such that Arthur accepts with probability at least 2/3.
2. 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]).

Contains NP and BPP (in fact also ∃BPP), and is contained in AM and in QMA.

Also contained in Σ₂P ∩ Π₂P.

There exists an oracle relative to which BQP is not in MA [Wat00].

Equals NP under a derandomization assumption: if E requires exponentially-sized circuits, then PromiseBPP = PromiseP, implying that MA = NP [IW97].

Shown in [San07] that MA/1 does not have circuits of size $n^{k}$ for any $k>0$. In the same paper, the result was used to show that MA/1 cannot be solved on more than a $1/2+1/{n^{k}}$ fraction of inputs having length $n$ by any circuit of size $n^{k}$. Finally, it was shown that MA does not have arithmetic circuits of size $n^{k}$.

See also: MA_E, MA_EXP.

---

MA^cc: Communication Complexity MA

Here, Alice and Bob collectively constitute "Arthur", and the cost of an MA^cc 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.)

Does not contain coNP^cc (first shown by [Kla03]).

It is open to prove that there exists an explicit two-party function whose MA^cc-type communication complexity is ω(n^1/2).

---

MA': Sparse MA

The subclass of MA such that for each input size n, there is a sparse set S_n that Merlin's proof string always belongs to (no matter what the input is).

Defined in [KST93], where it is also observed that if graph isomorphism is in P/poly, then the complement of graph isomorphism is in MA'.

---

MAC⁰: Majority of AC⁰

Same as AC⁰, except now we're allowed a single unbounded-fanin majority gate at the root.

Defined in [JKS02].

MAC⁰ is strictly contained in TC⁰ [ABF+94].

---

MA_E: Exponential-Time MA With Linear Exponent

Same as MA, except now Arthur is E instead of polynomial-time.

If MA_E = NEE then MA = NEXP ∩ coNEXP [IKW01].

---

MA_EXP: Exponential-Time MA

Same as MA, except now Arthur is EXP instead of polynomial-time, and the message from Merlin can be exponentially long.

There is a problem in MA_EXP that does not have polynomial-size circuits [BFT98]. On the other hand, there is an oracle relative to which every problem in MA_EXP does have polynomial-size circuits.

[MVW99] considered the best circuit lower bound obtainable for a problem in MA_EXP, using current techniques. They found that this bound is half-exponential: i.e. a function f such that f(f(n))=2ⁿ. Such functions exist, but are not expressible using standard asymptotic notation.

---

mAL: Monotone AL

Defined in [GS90]. Equals mP by definition.

---

MA_POLYLOG: 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 $O({\textrm {poly}}(\log n))$.

This class was used by [SM03] to show that if EXP has circuits of polynomial size, then EXP = MA.

---

MaxNP: Maximization NP

Has the same relation to NP as MaxSNP does to SNP.

Contains MaxPB.

The closure of MaxNP under PTAS reduction is APX [KMS+99], [CT94].

---

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].

The closure of MaxPB under PTAS reductions equals NPOPB [CKS+99].

---

MaxSNP: Maximization SNP

The class of optimization problems reducible by an "L-reduction" to a problem in MaxSNP₀. (Note: 'L' stands for linear -- this is not the same as an L reduction! For more details see [PY88].)

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.

The closure of MaxSNP under PTAS reduction is APX [KMS+99], [CT94].

---

MaxSNP₀: 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

Defined in [GS90], where it was also shown that mcoNL does not equal 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[2] = MIP [BGK+88].

MIP equals NEXP [BFL91]; this is a famous non-relativizing result.

---

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.

Defined in [CHT+04], where evidence was given suggesting that MIP* does not "obviously" equal NEXP.

MIP* contains NEXP [IV12]. By contrast, MIP, the corresponding class without entanglement, equals NEXP (and even MIP[2,1] with two provers and one round equals NEXP).

Even MIP*[4,poly] and MIP[5,1] contain NEXP [IV12].

MIP*[2,1] contains XOR-MIP*[2,1].

In 2012 it was shown that QMIP = MIP* [RUV12]

---

MIP_EXP: Exponential-Time Multi-Prover Interactive Proof

The exponential-time analogue of MIP.

In the unrelativized world, equals NEEXP.

There exists an oracle relative to which MIP_EXP equals the intersection of P/poly, P^NP, and ⊕P [BFT98].

---

(M_k)P: Acceptance Mechanism by Monoid M_k

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 (M_k)P is the class of decision problems solvable by an NP machine with the following acceptance mechanism. The i^th computation path (under some lexicographic ordering) outputs an element m_i of M_k. Then the machine accepts if and only if m₁m₂...m_s 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 S₅, the symmetric group on 5 elements), then (G)P = PSPACE.
• (Z_k)P = coMod_kP, where Z_k is the cyclic group on k elements.
• If |G|=k, then (G)P contains coMod_kP.

---

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.

Strictly contains mNC¹ [GS91].

Contained in (nonuniform versions of) mNL and mcoNL.

---

MM: Problems reducible to matrix multiplication

The set of all problems reducible to matrix multiplication. That is, the set of problems $P$ that can be reduced to the multiplication of two square matrices can be reduced to $P$ in linear time.

Currently, the best known algorithm for multiplying two $n\times n$ matrices is the Coppersmith–Winograd_algorithm, which has a time complexity of $O(n^{2.376})$ [CW90]. Note that for the general problem, a lower bound of $\Omega (n^{2})$ is trivial from the number of elements being considered.

---

MMSNP: Monadic Monotone SNP

Defined in [FV93] as a subclass of SNP. There are three syntactic restrictions defining the subclass MMSNP, based on the form of the SNP formula defining the language:

1. The second order existentially quantified variables, known as the proof relations, are restricted to be monadic. (Monadic relations can be treated as sets.)
2. Any relations in the formula other than the proof relations must occur only negated (the formula is monotone).
3. 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.

---

mNC¹: Monotone NC¹

The class of decision problems solvable by a family of monotone NC¹ circuits (i.e. AND and OR gates only).

A uniformity condition could also be imposed.

Defined in [GS90].

Strictly contained in mNL [KW88], and indeed in mL [GS91].

Strictly contains mTC⁰ [Yao89].

---

mNL: Monotone NL

See mP for the definition of a monotone nondeterministic Turing machine, due to [GS90].

mNL is the class of decision problems solvable by a monotone nondeterministic log-space Turing machine.

mNL does not equal mcoNL [GS90], in contrast to the case for NL and coNL.

Also, mNL strictly contains mNC¹ [KW88].

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.

Defined in [GS90], where it was also shown that mNP is 'trivial': that is, it contains exactly the monotone problems in NP.

Strictly contains mP [Raz85].

---

Mod_kL: Mod-k L

Has the same relation to L as Mod_kP does to P.

For any prime k, Mod_kL contains SL [KW93].

For any prime k, Mod_kL^ModkL = Mod_kL [HRV00].

For any k>1, contains LogFew [BDH+92].

---

ModL: ModL

A language $L\in {\mathsf {ModL}}$ if there are functions $f\in {\mathsf {GapL}}$ and $g\in {\mathsf {FL}}$ such that for all strings $x$:

• There exists a prime $p$ and a natural number $\alpha$ such that $g(x)=0^{p^{\alpha }}$.
• $x\in L$ if and only if $f(x)\equiv 0(\left|g(x)\right|)$.

Thus, for any prime $p$ and natural number $\alpha$, ${\mathsf {Mod}}_{p^{\alpha }}{\mathsf {L}}\subseteq {\mathsf {ModL}}$. Moreover, FL^ModL = FL^GapL [AV04].

Defined in [AV04].

---

Mod_kP: 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."

Mod₂P is more commonly known as ⊕P "parity-P."

For every k, Mod_kP contains graph isomorphism [AK02].

Defined in [CH89], [Her90].

[Her90] and [BG92] showed that Mod_kP is the set of unions of languages in Mod_pP for each prime p that divides k. In particular, if p is prime, then Mod_pP = Mod_p^mP for all positive integers m. A further fact is that Mod_pP 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 Mod_kP is not closed under intersection or complement [BBR94].

For prime p, there exists an oracle relative to which Mod_pP does not contain EQP [GV02].

---

ModP: Mod_kP With Arbitrary k

The class of decision problems solvable by a Mod_kP machine where k can vary depending on the input. The only requirement is that 0^k be computable in polynomial time.

Defined in [KT96], where it was also shown that ModP is contained in AmpMP.

---

ModZ_kL: Restricted Mod_kL

The class of decision problems solvable by a nondeterministic logspace Turing machine, such that

1. If the answer is "yes," then the number of accepting paths is not congruent to 0 mod k.
2. If the answer is "no," then there are no accepting paths.

Defined in [BDH+92], where it was also shown that ModZ_kL contains LogFewNL for all k>1.

Contained in Mod_kL and in NL.

---

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."

Then applying the result of [CKS81] that P = AL, mP is defined to be mAL: the class of decision problems solvable by a monotone alternating log-space Turing machine.

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.

Strictly contained in mNP [Raz85].

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.

See also: mNC¹, mL, mNL, mcoNL.

---

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].

Contains AmpMP and PH.

MP with ModP oracle equals MP with #P oracle [KT96].

---

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 (x₁,...,x_n).

Defined in [DC89].

[BLM+99] showed that we can assume without loss of generality that the circuit has width n and depth n³.

---

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.

---

mTC⁰: Monotone TC⁰

The class of decision problems solvable by a family of monotone TC⁰ 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].

Strictly contained in mNC¹ [Yao89].