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⁰ - LH - LIN - L_kP - 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¹ [Bor77], and is contained in generalizations including NL, L/poly, SL, RL, ⊕L, and Mod_kL.

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⁰: 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⁰, which has a linear number of wires.

It is properly contained in AC⁰ [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.

LH equals AC⁰ 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_kP: Low Hierarchy In NP

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

L₁P = NP ∩ coNP.

For all k, L_k is contained in L_k+1 and in NP.

Defined in [Sch83].

See also H_kP.

---

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¹ [Ven91]: LOGCFL is the class of decision problems solvable by a uniform family of AC¹ 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

1. The number of accepting paths on input x is f(x), and
2. 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_kL 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_kL 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 $Pi_{n}$ and $Sigma_{n}$ levels are incomparable unless $n=1$; 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₁,...,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₀ 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₀ under polynomial-time many-one reductions.

The motivation is that the analogue of LOGNP₀ 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 β₂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₁,...,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₀ 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₀ 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.

Equals PBP [Cob66].

Contains SL [AKL+79].

---

LWPP: Length-Dependent Wide PP

The class of decision problems solvable by an NP machine such that

1. If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.
2. 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.)

Contained in WPP and AWPP.

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