In
computational complexity theoryComputational 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 classIn 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
completeIn 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
NLIn 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
NLIn 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 spaceIn 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-connectivityIn 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-satisfiabilityIn 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 formIn 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.