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.
Defined in [GS90], where it was also shown that mcoNL does not equal mNL.
See also: mL.
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].
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.
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.