# 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 -
LC^{0} -
LH -
LIN -
L_{k}P -
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 NC^{1} [Bor77], and is contained in generalizations including NL, L/poly, SL, RL, ⊕L, and Mod_{k}L.

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.

##### LC^{0}: 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 WLC^{0}, which has a linear number of *wires*.

It is properly contained in AC^{0} [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 *i*th 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 *i*th 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.

LH equals AC^{0} and FO [Imm98].

##### LIN: Linear Time

The class of decision problems solvable by a deterministic Turing machine in linear time.

Strictly Contained in NLIN. [PPS+83].

##### L_{k}P: Low Hierarchy In NP

The class of problems A such that Σ_{k}P^{A} = Σ_{k}P; that is, adding A as an oracle does not increase the power of the k^{th} level of the polynomial hierarchy.

L_{1}P = NP ∩ coNP.

For all k, L_{k} is contained in L_{k+1} and in NP.

Defined in [Sch83].

See also H_{k}P.

##### 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 SAC^{1} [Ven91]: LOGCFL is the class of decision problems solvable by a uniform family of AC^{1} 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 Mod_{k}L 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 ModZ_{k}L 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={s

_{1},...,s

_{log 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,s

_{j},x,y,j) holds. Here x and y are logarithmic-length strings, or equivalently polynomially bounded numbers, and φ is computable in P.

LOGNP_{0} 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 LOGNP_{0} under polynomial-time many-one reductions.

The motivation is that the analogue of LOGNP_{0} 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 β_{2}P).

##### 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={s

_{1},...,s

_{log n}} of {1,...,n} of size log n, such that for all x there exists j in S such that the predicate φ(I,s

_{j},x,j) holds. Here x is a logarithmic-length string, or equivalently a polynomially bounded number, and φ is computable in P.

LOGSNP_{0} 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 LOGSNP_{0} 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].