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.
ACi is the class of decision problems solvable by a nonuniform family of Boolean circuits, with polynomial size, depth O(logi(n)), and unbounded fanin. The gates allowed are AND, OR, and NOT.
Then AC is the union of ACi over all nonnegative i.
ACi is contained in NCi+1; thus, AC = NC.
For a random oracle A, (ACi)A is strictly contained in (ACi+1)A, and (uniform) ACA is strictly contained in PA, with probability 1 [Mil92].
FO-uniform AC with depth is equal to FO[].
See AC for definition.
Contains NL (hence also NC1). Contained in NC2. The complexity class DET also obeys all these containment relationships, but no containment is known in either direction between AC1 and DET.
A comparator gate consists of two inputs and outputs the minimum of its two inputs on its first output wire and outputs the maximum of its two inputs on its second output wire. One important restriction is that each output of a comparator gate has fanout at most one. The Comparator Circuit Value Problem (CCVP) is defined as following. Given a circuit composed of comparator gates, the inputs to the circuit, and one output of the circuit, calculate the value of this output.
CC is defined as the class of problems log-space many-one reducible to CCVP [MS89]. At present it is only known that NLCCP [MS89]. CC is an example of a complexity class neither known to be in NC nor P-complete.
Natural complete problems for the CC class include Stable Marriage Problem, Stable Roommate Problem, Lex-first Maximal Matching [Sub94].
The class of decision problems reducible in L to the problem of computing the determinant of an n-by-n matrix of n-bit integers.
Defined in [Coo85]. (Cook used NC1 reductions in his definition)
Contained in NC2, and contains NL and PL [BCP83].
Graph isomorphism is hard for DET under L-reductions [Tor00].
The corresponding function class turns out to be equal to GapL (see refs at GapL), that is, the determinant of integer matrices is GapL-complete.
Has the same relation to NL as FNP does to NP.
Defined by [AJ93], who also showed that if NL = UL, then FNL is contained in #L.
FO(TC) is the set of boolean queries definable with first-order formulae with a transitive closure (TC) operator.
TC is defined this way: let be a positive integer and be vectors of variables, then TC( is true if there exist variables such that and for all . Here, is a formula over written in FO(TC) and means that the variables and are replaced by and .
Every formula of TC can be written in a normal form FO( where is a FO formula and we suppose that there is an order on the model where variables are quantified, so we can choose the minimum and maximum element.
It was shown in [Imm98] page 150 that this class is equal to NL.
The class of decision problems solvable by a uniform family of polynomial-size, unbounded-fanin, depth O(log log n) circuits with AND, OR, and NOT gates. Equals FO(log log n).
Defined in [BKL+00], where it was also shown that many problems on finite groups are in FOLL.
Contains uniform AC0, and is contained in uniform AC1.
Is not known to be comparable to L or NL.
The class of decision problems solvable by a Turing machine restricted to use an amount of memory logarithmic in the size of the input, n. (The input itself is not counted as part of the memory.)
L is contained in P. L contains NC1 [Bor77], and is contained in generalizations including NL, L/poly, SL, RL, ⊕L, and ModkL.
Reingold [Rei04] showed that, remarkably, L = SL. In other words, undirected graph connectivity is solvable in deterministic logarithmic space.
Immerman [Imm83] showed that L is the class FO(dtc) of first-order expressible queries with a deterministic transitive closure.
L queries are exactly the one that can be written in a syntactic restriction of While languages.
The class of decision problems reducible in L to the problem of deciding membership in a context-free language.
Equals uniform SAC1 [Ven91]: LOGCFL is the class of decision problems solvable by a uniform family of AC1 circuits, in which no AND gate has fan-in exceeding 2 (see e.g. [Joh90], p. 137).
LOGCFL is closed under complement [BCD+89]. For more on LOGCFL from the descriptive complexity viewpoint, including completeness results under FO reductions, see [LMSV01].
Contains NL [Sud78], and also the problem of recognizing graphs of bounded tree-width [Wan94].
The class of decision problems solvable by an NL machine such that
Defined in [BDH+92], where it was also shown that LogFew is contained in ModkL for all k>1.
Same as FewP but for logspace-bounded (i.e. NL) machines.
Defined in [BDH+92], where it was also shown that LogFewNL is contained in ModZkL for all k>1.
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 class of decision problems solvable by a nondeterministic logspace Turing machine, such that
Defined in [BDH+92], where it was also shown that ModZkL contains LogFewNL for all k>1.
(Named in honor of Nick Pippenger.)
NCi is the class of decision problems solvable by a uniform family of Boolean circuits, with polynomial size, depth O(logi(n)), and fan-in 2.
Then NC is the union of NCi over all nonnegative i.
Also, NC equals the union of PT/WK(logkn, nk)/poly over all constants k.
NCi is contained in ACi; thus, NC = AC.
Contains NL, in fact NL is contained in NC2.
Generalizations include RNC and QNC.
[IN96] construct a candidate pseudorandom generator in NC based on the subset sum problem.
For a random oracle A, (NCi)A is strictly contained in (NCi+1)A, and uniform NCA is strictly contained in PA, with probability 1 [Mil92].
In descriptive complexity, NC can be defined by FO[]
Log space uniform NC is contained in ATIME(poly(log(n))) = polyL [RUZ81].
See NC for definition.
Contains AC1 and DET, both of which contain NL. It seems we currently (as of this writing, 15 Jun 2022) do not know any problem in NC2 that's not known to be in AC1∪ DET (see this question).
Has the same relation to NL as P/poly does to P.
Is contained in ⊕L/poly [GW96], as well as SAC1.
The class of optimization problems which can be solved in nondeterministic logspace.
Defined in [TAN07] as the logspace equivalent of NPO, where it is shown that the various logspace approximation classes form a hierarchy iff L ≠ NL.
As with the definition of NPO in [ACG+99], NLO is defined as a class of "structured" problems, comprising both a "solution relation" (indicating which solutions are acceptable for a given input) and a "measure function" (computing the value of each solution). The equivalent "unstructured" class is OptL. See [TAN07] for discussion.
Same as NL -- but if there's an oracle, then NLOG can make queries nondeterministically on a polynomial-size, one-way oracle tape. (NL, by contrast, can use nondeterministic transitions only on the worktape; oracle queries have to be deterministic.)
See [LL76] or [HCK+88] for more information.
Although NLOG is contained in P, there exists an oracle relative to which that is not the case. This illustrates that care is needed when defining oracle access mechanisms.
The class that started it all.
The class of decision problems solvable in polynomial time by a Turing machine. (See also FP, for function problems.)
Defined in [Edm65], [Cob64], [Rab60], and other seminal early papers.
Contains some highly nontrivial problems, including linear programming [Kha79] and finding a maximum matching in a general graph [Edm65].
Contains the problem of testing whether an integer is prime [AKS02], an important result that improved on a proof requiring an assumption of the generalized Riemann hypothesis [Mil76].
A decision problem is P-complete if it is in P, and if every problem in P can be reduced to it in L (logarithmic space). The canonical P-complete problem is circuit evaluation: given a Boolean circuit and an input, decide what the circuit outputs when given the input.
Important subclasses of P include L, NL, NC, and SC.
P is contained in NP, but whether they're equal seemed to be an open problem when I last checked.
Efforts to generalize P resulted in BPP and BQP.
The nonuniform version is P/poly, the monotone version is mP, and versions over the real and complex number fields are PR and PC respectively.
In descriptive complexity, P can be defined by three different kind of formulae, FO(lfp) which is also FO()], and also as SO(Horn)
P queries are exactly the one that can be written in the While/cons languages.
P is the class of decision problems solvable by a (logspace) uniform family of polynomial-size Boolean circuits.
P can be computed by interactive protocols (see IP) where the verifier runs in log space (see L and BPL) [GKR15].
para- version of NL. Equivalent to NDSPACE(f(k)+log(n)) for some computable function f. Compare with slicewise parameterized nondeterministic logspace, XNL.
It seems open whether there are natural complete problems for para-NL. However, the related class para-NL[f log] has many natural complete problems.
Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also run in polynomial time (since otherwise we would just getNL).
Contains RHL.
[RTV05] give strong evidence that RL = L.
The class of problems solvable by a nondeterministic Turing machine in logarithmic space, such that
Defined in [LP82].
The undirected s-t connectivity problem (USTCON: is there a path from vertex s to vertex t in a given undirected graph?) is complete for SL, under L-reductions.
SL contains L, and is contained in NL.
It follows from [AKL+79] that SL is contained in L/poly.
[KW93] showed that SL is contained in ⊕L, as well as ModkL for every prime k.
SL is also contained in DSPACE(log3/2n) [NSW92], and indeed in DSPACE(log4/3n) [ATW+00].
[NT95] showed that SL equals coSL, and furthermore that SLSL = SL (that is, the symmetric logspace hierarchy collapses).
Reingold ultimately showed that SL = L [Rei04], even relative to an oracle. This subsumes many of the earlier results.
SO(krom) is the set of boolean queries definable with second-order formulae in normal form such that the quantifier-free part of the formula is in Krom form, which means that in every clause there is at most two literals and the first-order portion contains no existential quantifiers.
It was shown in [Grä92] that this class is equal to NL.
Those formulaes can be made in prenex form where the second order is existential and the first order universal without loss of generalities.
The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an NL machine.
Defined in [AJ93], where it is also shown that span-L is a hard class in the sense that span-L is contained in FP if and only if FP = #P.
Span-L is contained in #P, and if span-L = #P, then NL = NP [AJ93].
Span-L is contained in FPRAS [ACJ+21].
The class of problems reducible in L to the problem of whether an undirected graph has a unique connected component.
See [AG00] for more information.
The corresponding class for directed graphs equals NL. On the other hand, none of that class's corresponding search problems are obviously FNL-hard.
Has the same relation to L as UP does to P.
The problem of reachability in directed planar graphs lies in UL [SES05].
If UL = NL, then FNL is contained in #L [AJ93].
