Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

L (complexity)

Index L (complexity)

In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space. [1]

39 relations: Binary decision diagram, Cambridge University Press, Clique (graph theory), Complete (complexity), Complexity class, Computational complexity theory, Computational resource, Computers and Intractability, Connected component (graph theory), Decision problem, Directed graph, DNA, First-order logic, FL (complexity), FO (complexity), Function problem, Graph (discrete mathematics), Graph theory, L/poly, List of unsolved problems in computer science, Log-space reduction, Logarithm, Low (complexity), NC (complexity), NL (complexity), Non-deterministic Turing machine, Null (SQL), Omer Reingold, P (complexity), Pointer (computer programming), Query language, Random-access memory, Reachability, Relational algebra, Relational database, SL (complexity), Symposium on Theory of Computing, Transitive closure, Turing machine.

Binary decision diagram

In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function.

New!!: L (complexity) and Binary decision diagram · See more »

Cambridge University Press

Cambridge University Press (CUP) is the publishing business of the University of Cambridge.

New!!: L (complexity) and Cambridge University Press · See more »

Clique (graph theory)

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete.

New!!: L (complexity) and Clique (graph theory) · See more »

Complete (complexity)

In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class.

New!!: L (complexity) and Complete (complexity) · See more »

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.

New!!: L (complexity) and Complexity class · See more »

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: L (complexity) and Computational complexity theory · See more »

Computational resource

In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.

New!!: L (complexity) and Computational resource · See more »

Computers and Intractability

In computer science, more specifically computational complexity theory, Computers and Intractability: A Guide to the Theory of NP-Completeness is an influential textbook by Michael Garey and David S. Johnson.

New!!: L (complexity) and Computers and Intractability · See more »

Connected component (graph theory)

In graph theory, a connected component (or just 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 in the supergraph.

New!!: L (complexity) and Connected component (graph theory) · See more »

Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

New!!: L (complexity) and Decision problem · See more »

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is a set of vertices connected by edges, where the edges have a direction associated with them.

New!!: L (complexity) and Directed graph · See more »


Deoxyribonucleic acid (DNA) is a thread-like chain of nucleotides carrying the genetic instructions used in the growth, development, functioning and reproduction of all known living organisms and many viruses.

New!!: L (complexity) and DNA · See more »

First-order logic

First-order logic—also known as first-order predicate calculus and predicate logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science.

New!!: L (complexity) and First-order logic · See more »

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.

New!!: L (complexity) and FL (complexity) · See more »

FO (complexity)

In descriptive complexity, a branch of computational complexity, FO is a complexity class of structures that can be recognized by formulas of first-order logic, and also equals the complexity class AC0.

New!!: L (complexity) and FO (complexity) · See more »

Function problem

In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem.

New!!: L (complexity) and Function problem · See more »

Graph (discrete mathematics)

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".

New!!: L (complexity) and Graph (discrete mathematics) · See more »

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

New!!: L (complexity) and Graph theory · See more »


In computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice.

New!!: L (complexity) and L/poly · See more »

List of unsolved problems in computer science

This article is a list of unsolved problems in computer science.

New!!: L (complexity) and List of unsolved problems in computer science · See more »

Log-space reduction

In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space.

New!!: L (complexity) and Log-space reduction · See more »


In mathematics, the logarithm is the inverse function to exponentiation.

New!!: L (complexity) and Logarithm · See more »

Low (complexity)

In computational complexity theory, a language B (or a complexity class B) is said to be low for a complexity class A (with some reasonable relativized version of A) if AB.

New!!: L (complexity) and Low (complexity) · See more »

NC (complexity)

In complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors.

New!!: L (complexity) and NC (complexity) · See more »

NL (complexity)

In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.

New!!: L (complexity) and NL (complexity) · See more »

Non-deterministic Turing machine

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers.

New!!: L (complexity) and Non-deterministic Turing machine · See more »

Null (SQL)

Null (or NULL) is a special marker used in Structured Query Language to indicate that a data value does not exist in the database.

New!!: L (complexity) and Null (SQL) · See more »

Omer Reingold

Omer Reingold (עומר ריינגולד) is a faculty member of the Computer Science Department at Stanford University.

New!!: L (complexity) and Omer Reingold · See more »

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.

New!!: L (complexity) and P (complexity) · See more »

Pointer (computer programming)

In computer science, a pointer is a programming language object that stores the memory address of another value located in computer memory.

New!!: L (complexity) and Pointer (computer programming) · See more »

Query language

Query languages or data query languages (DQLs) are computer languages used to make queries in databases and information systems.

New!!: L (complexity) and Query language · See more »

Random-access memory

Random-access memory (RAM) is a form of computer data storage that stores data and machine code currently being used.

New!!: L (complexity) and Random-access memory · See more »


In graph theory, reachability refers to the ability to get from one vertex to another within a graph.

New!!: L (complexity) and Reachability · See more »

Relational algebra

Relational algebra, first created by Edgar F. Codd while at IBM, is a family of algebras with a well-founded semantics used for modelling the data stored in relational databases, and defining queries on it.

New!!: L (complexity) and Relational algebra · See more »

Relational database

A relational database is a digital database based on the relational model of data, as proposed by E. F. Codd in 1970.

New!!: L (complexity) and Relational database · See more »

SL (complexity)

In computational complexity theory, SL (Symmetric Logspace or Sym-L) is the complexity class of problems log-space reducible to USTCON (undirected s-t connectivity), 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 same connected component.

New!!: L (complexity) and SL (complexity) · See more »

Symposium on Theory of Computing

The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science.

New!!: L (complexity) and Symposium on Theory of Computing · See more »

Transitive closure

In mathematics, the transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive.

New!!: L (complexity) and Transitive closure · See more »

Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

New!!: L (complexity) and Turing machine · See more »

Redirects here:

Deterministic logspace, L (class), L (complexity class), L (complexity theory), LOGSPACE, LSPACE, Log space, Logarithmic space, Logspace.


[1] https://en.wikipedia.org/wiki/L_(complexity)

Hey! We are on Facebook now! »