Class Description

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 mNC1 [GS91].

Contained in (nonuniform versions of) mNL and mcoNL.

Linked From

mcoNL: Complement of mNL

Defined in [GS90], where it was also shown that mcoNL does not equal mNL.

See also: mL.

More about...


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

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

Strictly contains mTC0 [Yao89].

More about...


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 mNC1 [KW88].

See also: mL.

More about...


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: mNC1, mL, mNL, mcoNL.

More about...