# Difference between revisions of "Complexity Zoo:M"

m |
(→MAcc: Communication Complexity MA) |
||

Line 27: | Line 27: | ||

===== <span id="macc" style="color:red">MA<sup>cc</sup></span>: Communication Complexity [[#ma|MA]] ===== | ===== <span id="macc" style="color:red">MA<sup>cc</sup></span>: Communication Complexity [[#ma|MA]] ===== | ||

+ | |||

+ | Here, Alice and Bob collectively constitute "Arthur", and the cost of an MA<sup>cc</sup> 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 [[Complexity Zoo:C#conpcc|coNP<sup>cc</sup>]] (first shown by [[zooref#kla03|[Kla03]]]). | ||

+ | |||

+ | It is open to prove that there exists an explicit function whose MA<sup>cc</sup>-type communication complexity is ω(n<sup>1/2</sup>). | ||

---- | ---- |

## Revision as of 21:04, 9 June 2016

*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^{0} -
MA_{E} -
MA_{EXP} -
mAL -
MA_{POLYLOG} -
MaxNP -
MaxPB -
MaxSNP -
MaxSNP_{0} -
mcoNL -
MinPB -
MIP -
MIP*[2,1] -
MIP^{ns} -
MIP_{EXP} -
(M_{k})P -
mL -
MM -
MMSNP -
mNC^{1} -
mNL -
mNP -
Mod_{k}L -
ModL -
Mod_{k}P -
ModP -
ModZ_{k}L -
mP -
MP -
MPC -
mP/poly -
mTC^{0}

##### 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

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

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

Also contained in Σ_{2}P ∩ Π_{2}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 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 .

##### 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 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^{0}: Majority of AC^{0}

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

Defined in [JKS02].

MAC^{0} is strictly contained in TC^{0} [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^{n}. 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 .

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_{0}. (*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_{0}: 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_{1}m_{2}...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
_{5}, the symmetric group on 5 elements), then (G)P = PSPACE. - (Z
_{k})P = coMod_{k}P, where Z_{k}is the cyclic group on k elements. - If |G|=k, then (G)P contains coMod
_{k}P.

##### 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^{1} [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 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

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:

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

##### mNC^{1}: Monotone NC^{1}

The class of decision problems solvable by a family of monotone NC^{1} 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^{0} [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^{1} [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.

##### Mod_{k}L: Mod-k L

Has the same relation to L as Mod_{k}P does to P.

For any prime k, Mod_{k}L contains SL [KW93].

For any prime k, Mod_{k}L^{ModkL} = Mod_{k}L [HRV00].

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

##### ModL: ModL

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 .

Thus, for any prime and natural number , . Moreover, FL^{ModL} = FL^{GapL} [AV04].

Defined in [AV04].

##### Mod_{k}P: 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_{2}P is more commonly known as ⊕P "parity-P."

For every k, Mod_{k}P contains graph isomorphism [AK02].

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

For prime p, there exists an oracle relative to which Mod_{p}P does not contain EQP [GV02].

##### ModP: Mod_{k}P With Arbitrary k

The class of decision problems solvable by a Mod_{k}P 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_{k}L: Restricted Mod_{k}L

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.

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

Contained in Mod_{k}L 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^{1}, 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].

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_{1},...,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^{3}.

##### 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^{0}: Monotone TC^{0}

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