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.
NL is to L as NP is to P. Not known whether a particular relation (equality or inequality) between P and NP implies the same relation between L and NL.
In a breakthrough result, was shown to equal coNL [Imm88] [Sze87]. (Though contrast to mNL.)
Is contained in LOGCFL [Sud78], as well as NC2.
Is contained in UL/poly [RA00].
Deciding whether a bipartite graph has a perfect matching is hard for NL [KUW86].
NL can be defined in a logical formalism as SO(krom) and also as FO(tc), reachability in directed graph is NL-Complete under FO-reduction.