L (complexity)
Encyclopedia
In computational complexity theory
, L (also known as LSPACE) is the complexity class
containing decision problem
s which can be solved by a deterministic Turing machine using a logarithm
ic amount of memory space. Logarithmic space is sufficient to hold a constant number of pointers into the input and a logarithmic number of boolean flags and many basic logspace algorithms use the memory in this way.
L is a subclass of NL
, which is the class of languages decidable in logarithm
ic space on a nondeterministic Turing machine. Using the construction of Savitch's theorem
, one can see that NL is contained in the complexity class P
of problems solvable in deterministic polynomial time. Thus L ⊆ NL ⊆ P. The inclusion of L into P can also be proved more directly: a decider using O(log n) space cannot use more than 2O(log n) = nO(1) time, because this is the total number of possible configurations.
Every non-trivial problem in L is complete
under log-space reduction
s so weaker reductions are required to identify meaningful notions of L-completeness. These include NC1
-reductions and DLOGTIME
-reductions.
Important open problems include whether L = P, and whether L = NL.
The related class of function problem
s is FL
. FL is often used to define logspace reductions.
A breakthrough October 2004 paper by Omer Reingold
showed that USTCON, the problem of whether there exists a path between two vertices in a given undirected graph, is in L, establishing that L = SL
, since USTCON is SL-complete.
One consequence of this is a simple logical characterization of L: it contains precisely those languages expressible in first-order logic
with an added commutative transitive closure
operator (in graph theoretical
terms, this turns every connected component
into a clique
).
L is low
for itself, because it can simulate log-space oracle queries (roughly speaking, "function calls which use log space") in log space, reusing the same space for each query.
The logspace class is therefore useful to model computation where the input is too big to fit in the RAM
of a computer. Long DNA
sequences and databases are good examples of problems where only a constant part of the input will be in RAM at a given time and where we have pointers to compute the next part of the input to inspect, thus using only logarithmic memory.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, L (also known as LSPACE) is the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
containing decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s which can be solved by a deterministic Turing machine using a logarithm
Logarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
ic amount of memory space. Logarithmic space is sufficient to hold a constant number of pointers into the input and a logarithmic number of boolean flags and many basic logspace algorithms use the memory in this way.
L is a subclass of NL
NL (complexity)
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
, which is the class of languages decidable in logarithm
Logarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
ic space on a nondeterministic Turing machine. Using the construction of Savitch's theorem
Savitch's theorem
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, states that for any function ƒ ≥ log,...
, one can see that NL is contained in the complexity class P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
of problems solvable in deterministic polynomial time. Thus L ⊆ NL ⊆ P. The inclusion of L into P can also be proved more directly: a decider using O(log n) space cannot use more than 2O(log n) = nO(1) time, because this is the total number of possible configurations.
Every non-trivial problem in L is complete
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class...
under log-space reduction
Log-space reduction
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a logarithmic number of fixed-size integers...
s so weaker reductions are required to identify meaningful notions of L-completeness. These include NC1
NC (complexity)
In complexity theory, the class NC is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem is in NC if there exist constants c and k such that it can be solved in time O using O parallel processors...
-reductions and DLOGTIME
DLOGTIME
DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine. It is the smallest nontrivial class using the resource of deterministic time...
-reductions.
Important open problems include whether L = P, and whether L = NL.
The related class of function problem
Function problem
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
s is FL
FL (complexity)
In computational complexity theory, the complexity class FL is the set of function problems which can be solved by a deterministic Turing machine in a logarithmic amount of memory space...
. FL is often used to define logspace reductions.
A breakthrough October 2004 paper by Omer Reingold
Omer Reingold
Omer Reingold is a faculty member of the Foundations of Computer Science Group at the Weizmann Institute of Science, Israel. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs...
showed that USTCON, the problem of whether there exists a path between two vertices in a given undirected graph, is in L, establishing that L = SL
SL (complexity)
In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON , which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the...
, since USTCON is SL-complete.
One consequence of this is a simple logical characterization of L: it contains precisely those languages expressible in first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
with an added commutative transitive closure
Transitive closure
In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...
operator (in graph theoretical
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
terms, this turns every connected component
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
into a clique
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
).
L is low
Low (complexity)
In computational complexity theory, a complexity class B is said to be low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve...
for itself, because it can simulate log-space oracle queries (roughly speaking, "function calls which use log space") in log space, reusing the same space for each query.
Use outside of complexity world
The main idea of logspace is that you can mostly count things up to a polynomial number using logspace and remember pointers to position of the input.The logspace class is therefore useful to model computation where the input is too big to fit in the RAM
Random-access memory
Random access memory is a form of computer data storage. Today, it takes the form of integrated circuits that allow stored data to be accessed in any order with a worst case performance of constant time. Strictly speaking, modern types of DRAM are therefore not random access, as data is read in...
of a computer. Long DNA
DNA
Deoxyribonucleic acid is a nucleic acid that contains the genetic instructions used in the development and functioning of all known living organisms . The DNA segments that carry this genetic information are called genes, but other DNA sequences have structural purposes, or are involved in...
sequences and databases are good examples of problems where only a constant part of the input will be in RAM at a given time and where we have pointers to compute the next part of the input to inspect, thus using only logarithmic memory.
See also
- L/polyL/polyIn computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice. L/poly is a non-uniform logarithmic space class, analogous to the non-uniform polynomial time class P/poly....
, a nonuniform variant of L that captures the complexity of polynomial-size branching programs