Table of Contents
42 relations: AC (complexity), Algorithm, Cem Say, Certificate (complexity), 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, Kleene star, L (complexity), List of unsolved problems in computer science, Log-space reduction, Logarithm, Logical disjunction, NC (complexity), Neil Immerman, NL (complexity), NL-complete, Nondeterministic Turing machine, NP (complexity), NSPACE, Open problem, P (complexity), Probabilistic Turing machine, Propositional calculus, 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. NL (complexity) and aC (complexity) are complexity classes.
See NL (complexity) and AC (complexity)
Algorithm
In mathematics and computer science, an algorithm is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation.
See NL (complexity) and Algorithm
Cem Say
Ahmet Celal Cem Say (born 14 March 1966 in Ankara) is a Turkish theoretical computer scientist and professor of computer science.
See NL (complexity) and Cem Say
Certificate (complexity)
In computational complexity theory, a certificate (also called a witness) is a string that certifies the answer to a computation, or certifies the membership of some string in a language.
See NL (complexity) and Certificate (complexity)
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 the Boolean circuits that compute them.
See NL (complexity) and Circuit complexity
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers.
See NL (complexity) and Complement (complexity)
Complexity class
In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". NL (complexity) and complexity class are complexity classes.
See NL (complexity) and Complexity class
Computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other.
See NL (complexity) and Computational complexity theory
Computational resource
In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.
See NL (complexity) and Computational resource
Decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values.
See NL (complexity) and Decision problem
Directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
See NL (complexity) and Directed graph
Expected value
In probability theory, the expected value (also called expectation, expectancy, expectation operator, mathematical expectation, mean, expectation value, or first moment) is a generalization of the weighted average.
See NL (complexity) and Expected value
First-order logic
First-order logic—also called predicate logic, predicate calculus, quantificational logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science.
See NL (complexity) and First-order logic
Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT).
See NL (complexity) and Gödel Prize
Immerman–Szelepcsényi theorem
In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation.
See NL (complexity) and Immerman–Szelepcsényi theorem
Kleene star
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters.
See NL (complexity) and Kleene star
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. NL (complexity) and l (complexity) are complexity classes.
See NL (complexity) and L (complexity)
List of unsolved problems in computer science
This article is a list of notable unsolved problems in computer science.
See NL (complexity) and List of unsolved problems in computer science
Log-space reduction
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space.
See NL (complexity) and Log-space reduction
Logarithm
In mathematics, the logarithm is the inverse function to exponentiation.
See NL (complexity) and Logarithm
Logical disjunction
In logic, disjunction, also known as logical disjunction or logical or or logical addition or inclusive disjunction, is a logical connective typically notated as \lor and read aloud as "or".
See NL (complexity) and Logical disjunction
NC (complexity)
In computational 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. NL (complexity) and nC (complexity) are complexity classes.
See NL (complexity) and NC (complexity)
Neil Immerman
Neil Immerman (born 24 November 1953, Manhasset, New York) is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst.
See NL (complexity) and Neil Immerman
NL (complexity)
In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. NL (complexity) and nL (complexity) are complexity classes.
See NL (complexity) and NL (complexity)
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. NL (complexity) and nL-complete are complexity classes.
See NL (complexity) and NL-complete
Nondeterministic Turing machine
In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations.
See NL (complexity) and Nondeterministic Turing machine
NP (complexity)
In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NL (complexity) and NP (complexity) are complexity classes.
See NL (complexity) and NP (complexity)
NSPACE
In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine. NL (complexity) and NSPACE are complexity classes.
See NL (complexity) and NSPACE
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 (i.e., no solution for it is known).
See NL (complexity) and Open problem
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. NL (complexity) and p (complexity) are complexity classes.
See NL (complexity) and P (complexity)
Probabilistic Turing machine
In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution.
See NL (complexity) and Probabilistic Turing machine
Propositional calculus
The propositional calculus is a branch of logic.
See NL (complexity) and Propositional calculus
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. NL (complexity) and PSPACE are complexity classes.
See NL (complexity) and PSPACE
Róbert Szelepcsényi
Róbert Szelepcsényi (born 19 August 1966, Žilina) is a Slovak computer scientist of Hungarian descent and a member of the Faculty of Mathematics, Physics and Informatics of Comenius University in Bratislava.
See NL (complexity) and Róbert Szelepcsényi
Reachability
In graph theory, reachability refers to the ability to get from one vertex to another within a graph.
See NL (complexity) and Reachability
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.
See NL (complexity) and RL (complexity)
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.
See NL (complexity) and Savitch's theorem
St-connectivity
In computer science, 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.
See NL (complexity) and St-connectivity
Time complexity
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm.
See NL (complexity) and Time complexity
Transitive closure
In mathematics, the transitive closure of a homogeneous binary relation on a set is the smallest relation on that contains and is transitive.
See NL (complexity) and Transitive closure
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules.
See NL (complexity) and Turing machine
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.
See NL (complexity) and 2-satisfiability
References
Also known as Conl-complete, NL (complexity class), NL (complexity theory), NLOGSPACE, NLSPACE, Nlog, Nondeterministic logarithmic space, Nondeterministic logspace, ZPL (complexity).