NL-complete
Encyclopedia
In computational complexity theory
, NL-Complete is a complexity class
which is complete
for NL
. It contains the most "difficult" or "expressive" problems in NL
. If a method exists for solving any one of the NL-complete problems in logarithmic memory space
, then NL=L.
One important NL-complete problem is ST-connectivity
(or "Reachability") (Papadimitriou 1994 Thrm. 16.2), the problem of determining whether, given a directed graph G and two nodes s and t on that graph, there is a path from s to t. ST-connectivity can be seen to be in NL, because we start at the node s and nondeterministically walk to every other reachable node. ST-connectivity can be seen to be NL-hard by considering the computation state graph of any other NL algorithm, and considering that the other algorithm will accept if and only if there is a (nondetermistic) path from the starting state to an accepting state.
Another important NL-complete problem is 2-satisfiability
(Papadimitriou 1994 Thrm. 16.3), the problem of determining whether a boolean formula in conjunctive normal form
with two variables per clause is satisfiable.
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...
, NL-Complete is a 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:...
which 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...
for 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....
. It contains the most "difficult" or "expressive" problems in 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....
. If a method exists for solving any one of the NL-complete problems in logarithmic memory space
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
, then NL=L.
One important NL-complete problem is ST-connectivity
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- Complexity :...
(or "Reachability") (Papadimitriou 1994 Thrm. 16.2), the problem of determining whether, given a directed graph G and two nodes s and t on that graph, there is a path from s to t. ST-connectivity can be seen to be in NL, because we start at the node s and nondeterministically walk to every other reachable node. ST-connectivity can be seen to be NL-hard by considering the computation state graph of any other NL algorithm, and considering that the other algorithm will accept if and only if there is a (nondetermistic) path from the starting state to an accepting state.
Another important NL-complete problem is 2-satisfiability
2-satisfiability
In computer science, 2-satisfiability is the problem of determining whether a collection of two-valued variables with constraints on pairs of variables can be assigned values satisfying all the constraints...
(Papadimitriou 1994 Thrm. 16.3), the problem of determining whether a boolean formula in conjunctive normal form
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
with two variables per clause is satisfiable.