Complexity Zoo:L
Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References
Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z
Lists of related classes: Communication Complexity - Hierarchies - Nonuniform
L - LC0 - LH - LIN - LkP - LOGCFL - LogFew - LogFewNL - LOGLOG - LOGNP - LOGSNP - L/poly - LWPP
L: Logarithmic Space
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.
LC0: Unbounded Fanin Linear Size (gates) Constant-Depth Circuits
The class of decision problems solvable by a nonuniform family of Boolean circuits, with a linear number of gates, constant depth and unbounded fanin. Not to be confused with WLC0, which has a linear number of wires.
It is properly contained in AC0 [CR96].
LH: Logarithmic Time Hierarchy
A logarithmic-time alternating Turing machine is an alternating Turing machine that halts in logarithmic time, assuming the model of computation in which the machine has a special query tape on which it can write the binary integer i and receive the ith bit of the input string as a response, thus allowing any bit of an input string of length n to be read in time logarithmic in n. (There are other ways of defining the model of computation; see [RV97].)
The ith level of the Logarithmic Time Hierarchy is the set of languages recognised by a logarithmic-time alternating Turing machine making at most i alternations, beginning with existential state. LH is the union of all levels of the hierarchy.
LIN: Linear Time
The class of decision problems solvable by a deterministic Turing machine in linear time.
Strictly Contained in NLIN. [PPS+83].
LkP: Low Hierarchy In NP
The class of problems A such that ΣkPA = ΣkP; that is, adding A as an oracle does not increase the power of the kth level of the polynomial hierarchy.
L1P = NP ∩ coNP.
For all k, Lk is contained in Lk+1 and in NP.
Defined in [Sch83].
See also HkP.
LOGCFL: Logarithmically Reducible to CFL
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].
LogFew: Logspace-Bounded Few
The class of decision problems solvable by an NL machine such that
- The number of accepting paths on input x is f(x), and
- The answer is 'yes' if and only if R(x,f(x))=1, where R is some predicate computable in L.
Defined in [BDH+92], where it was also shown that LogFew is contained in ModkL for all k>1.
LogFewNL: Logspace-Bounded FewP
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.
LOGLOG: loglog Space
There are several possible definitions of this class; the most common is the class of languages which can be computed in space O(log log n) by a deterministic Turing machine with two-way access to the input. A typical nonregular language in this class has a form such as 00..00a00..01b00..10b00..11a..., with the successive numbers having logarithmic length. It is the smallest of a collection of sublogarithmically bounded space classes, since any smaller space class contains only the regular languages. These and related classes are studied extensively in [Szep94] and [LiRe93]. The alternation hierarchy for this class is infinite ([BGR93]), and the and levels are incomparable unless ; however, the nondeterministic version of the class is closed under complement ([Geff91]).
Sublogarithmically-bounded Turing reductions are equivalent to "regular" (constant-bounded) reductions, however ([Agr01]).
Note that while there are no decision problems that can be tested in one-way loglog space, there are promise problems which can be so tested, such as Balanced Monotone Boolean Sentence Value [Buss91]. Also, the alternation hierarchy over 1-way loglog space still does not collapse.
Obviously contained in L.
LOGNP: Logarithmically-Restricted NP
The class of decision problems expressible in logical form as
- The set of I for which there exists a subset S={s1,...,slog n} of {1,...,n} of size log n, such that for all x there exists y such that for all j in S, the predicate φ(I,sj,x,y,j) holds. Here x and y are logarithmic-length strings, or equivalently polynomially bounded numbers, and φ is computable in P.
LOGNP0 is the subclass in which φ is a first-order predicate without quantifiers and x and y are bounded lists of indices of input bits. LOGNP is also the closure of LOGNP0 under polynomial-time many-one reductions.
The motivation is that the analogue of LOGNP0 without the logarithmic bound on |S| is SO-E, which by Fagin's theorem equals NP [Fag74].
Defined in [PY96], where it was also shown that the following problem is complete for LOGNP under many-one reductions:
- Vapnik-Chervonenkis (V-C) Dimension. Given a family F of subsets of a set U, find a subset of S of U of maximum cardinality, such that every subset of S can be written as the intersection of S with some set in F.
Contains LOGSNP, and is contained in βP (indeed β2P).
LOGSNP: Logarithmically-Restricted SNP
The class of decision problems expressible in logical form as
- The set of I for which there exists a subset S={s1,...,slog n} of {1,...,n} of size log n, such that for all x there exists j in S such that the predicate φ(I,sj,x,j) holds. Here x is a logarithmic-length string, or equivalently a polynomially bounded number, and φ is computable in P.
LOGSNP0 is the subclass in which φ is a first-order predicate without quantifiers and x is a bounded lists of indices of input bits. LOGSNP is also the closure of LOGSNP0 under polynomial-time many-one reductions. See LOGNP and SNP for the motivation.
Defined in [PY96].
Contained in LOGNP, and therefore QPLIN.
If P = LOGSNP, then for every constructible f(n) > n, NTIME(f(n)) is contained in DTIME(g(n)sqrt(g(n))), where g(n) = O(f(n) logf(n)) [FK97].
L/poly: Nonuniform Logarithmic Space
Has the same relation to L as P/poly does to P.
LWPP: Length-Dependent Wide PP
The class of decision problems solvable by an NP machine such that
- If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.
- If the answer is "yes," then the difference of these numbers equals a function f(|x|) computable in polynomial time (i.e. FP). Here |x| is the length of the input x, and ``polynomial time means polynomial in |x|, the length of x, rather than the length of |x|.
Defined in [FFK94], where it was also shown that LWPP is low for PP and C=P. (I.e. adding LWPP as an oracle does not increase the power of these classes.)
Contains SPP.
Also, contains the graph isomorphism problem [KST92].
Contains a whole litter of problems for solvable black-box groups: group intersection, group factorization, coset intersection, and double-coset membership [Vin04].