Complexity Zoo:L
From Qwiki
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 - LIN - LkP - LOGCFL - LogFew - LogFewNL - 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 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.
LIN: Linear Time
The class of decision problems solvable by a deterministic Turing machine in linear time.
Contained in NLIN.
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.
Equivalently, 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].
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.
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, 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 many-one reduction.
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-Chernonenkis (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 such that the predicate φ(I,sj,x,j) holds. Here x and y are logarithmic-length strings, or equivalently polynomially bounded numbers, 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 many-one reduction. 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].
