Faster access than browser!
38 relations: AC (complexity), Algorithm, Circuit complexity, Complement (complexity), Complexity class, Computational complexity theory, Computational resource, Decision problem, Directed graph, Expected value, First-order logic, Gödel Prize, Immerman–Szelepcsényi theorem, L (complexity), List of unsolved problems in computer science, Log-space reduction, Logarithm, Logical disjunction, Michael Sipser, NC (complexity), Neil Immerman, NL (complexity), NL-complete, Non-deterministic Turing machine, NSPACE, Open problem, P (complexity), Probabilistic Turing machine, PSPACE, Róbert Szelepcsényi, Reachability, RL (complexity), Savitch's theorem, St-connectivity, Time complexity, Transitive closure, Turing machine, 2-satisfiability.
AC (complexity)
In circuit complexity, AC is a complexity class hierarchy.
New!!: NL (complexity) and AC (complexity) · See more »
Algorithm
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
New!!: NL (complexity) and Algorithm · See more »
Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them.
New!!: NL (complexity) and Circuit complexity · See more »
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers.
New!!: NL (complexity) and Complement (complexity) · See more »
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.
New!!: NL (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!!: NL (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!!: NL (complexity) and Computational resource · 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!!: NL (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!!: NL (complexity) and Directed graph · See more »
Expected value
In probability theory, the expected value of a random variable, intuitively, is the long-run average value of repetitions of the experiment it represents.
New!!: NL (complexity) and Expected value · 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!!: NL (complexity) and First-order logic · See more »
Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT).
New!!: NL (complexity) and Gödel Prize · See more »
Immerman–Szelepcsényi theorem
In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation.
New!!: NL (complexity) and Immerman–Szelepcsényi theorem · See more »
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.
New!!: NL (complexity) and L (complexity) · See more »
List of unsolved problems in computer science
This article is a list of unsolved problems in computer science.
New!!: NL (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!!: NL (complexity) and Log-space reduction · See more »
Logarithm
In mathematics, the logarithm is the inverse function to exponentiation.
New!!: NL (complexity) and Logarithm · See more »
Logical disjunction
In logic and mathematics, or is the truth-functional operator of (inclusive) disjunction, also known as alternation; the or of a set of operands is true if and only if one or more of its operands is true.
New!!: NL (complexity) and Logical disjunction · See more »
Michael Sipser
Michael Fredric Sipser (born September 17, 1954) is a theoretical computer scientist who has made early contributions to computational complexity theory.
New!!: NL (complexity) and Michael Sipser · 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!!: NL (complexity) and NC (complexity) · See more »
Neil Immerman
Neil Immerman (24 November 1953, Manhasset, New York) is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst.
New!!: NL (complexity) and Neil Immerman · 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!!: NL (complexity) and NL (complexity) · See more »
NL-complete
In computational complexity theory, NL-complete is a complexity class containing the languages that are complete for NL, the class of decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.
New!!: NL (complexity) and NL-complete · 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!!: NL (complexity) and Non-deterministic Turing machine · See more »
NSPACE
In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine.
New!!: NL (complexity) and NSPACE · See more »
Open problem
In science and mathematics, an open problem or an open question is a known problem which can be accurately stated, and which is assumed to have an objective and verifiable solution, but which has not yet been solved (no solution for it is known).
New!!: NL (complexity) and Open problem · See more »
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.
New!!: NL (complexity) and P (complexity) · See more »
Probabilistic Turing machine
In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which chooses between the available transitions at each point according to some probability distribution.
New!!: NL (complexity) and Probabilistic Turing machine · See more »
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
New!!: NL (complexity) and PSPACE · See more »
Róbert Szelepcsényi
Róbert Szelepcsényi (born 19 August 1966, Žilina) was a Slovak student of Hungarian descent and a member of the Faculty of Mathematics, Physics and Informatics of Comenius University in Bratislava.
New!!: NL (complexity) and Róbert Szelepcsényi · See more »
Reachability
In graph theory, reachability refers to the ability to get from one vertex to another within a graph.
New!!: NL (complexity) and Reachability · See more »
RL (complexity)
Randomized Logarithmic-space (RL), sometimes called RLP (Randomized Logarithmic-space Polynomial-time), is the complexity class of computational complexity theory problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with one-sided error.
New!!: NL (complexity) and RL (complexity) · See more »
Savitch's theorem
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity.
New!!: NL (complexity) and Savitch's theorem · See more »
St-connectivity
In computer science and computational complexity theory, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s. Formally, the decision problem is given by.
New!!: NL (complexity) and St-connectivity · See more »
Time complexity
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
New!!: NL (complexity) and Time complexity · 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!!: NL (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!!: NL (complexity) and Turing machine · See more »
2-satisfiability
In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables.
New!!: NL (complexity) and 2-satisfiability · See more »
Redirects here:
Conl-complete, NL (complexity class), NL (complexity theory), Nlog, Nondeterministic logarithmic space, Nondeterministic logspace, ZPL (complexity).
References
[1] https://en.wikipedia.org/wiki/NL_(complexity)
