Class Description

coNL: Complement of NL

Equals NL [Imm88] [Sze87].

Linked From

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


NL: Nondeterministic Logarithmic-Space

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.

More about...