Difference between revisions of "Complexity Zoo:L"

From Complexity Zoo
Jump to navigation Jump to search
(adds polynomial time bound to many-one reductions)
(updates logarithmic hierarchy entry)
Line 23: Line 23:
  
 
===== <span id="lh" style="color:red">LH</span>: Logarithmic Time Hierarchy =====
 
===== <span id="lh" style="color:red">LH</span>: Logarithmic Time Hierarchy =====
A Turing machine with random access owns a special tape where it can write a binary number <math>n</math>, and it can query the value of the <math>n</math>th bit of the input. Hence any bit of the input can be read in only logtime.
 
  
The <math>i</math>th level of the Logarithmic Time Hierarchy is the set of languages recognised by alternating Turing machine in logtime with random access and <math>i-1</math> alternation, begining with existantial state. LH is the union of all levels and is equal to tothe class [[#Complexity_Zoo:A#AC|AC<sup>0</sup>]] and to [[#Complexity_Zoo:F#FO|FO]] [[zooref#imm98|Descriptive complexity]].
+
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 [[zooref#rv97|[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 [[#Complexity_Zoo:A#AC|AC<sup>0</sup>]] and [[#Complexity_Zoo:F#FO|FO]] [[zooref#imm98|[Imm98]]].
  
 
----
 
----

Revision as of 21:48, 29 March 2016

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 Constant-Depth Circuits

The class of decision problems solvable by a nonuniform family of Boolean circuits, with linear size, constant depth and unbounded fanin.

It is equivalent to AC0 with bounded fanout and 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.

LH equals AC0 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].


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

Contains NL [Sud78].


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

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