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.

Related Topics:
Computational complexity theory - NL - Complexity class - Decision problem - Nondeterministic Turing machine - Logarithm - Memory space

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

NL is a generalization of L, the class for logspace problems on a deterministic Turing machine. Since any deterministic Turing machine is also a nondeterministic Turing machine, we have that L is contained in NL.

Related Topics:
L - Deterministic Turing machine - Nondeterministic Turing machine

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

STConnectivity, (or Reachability), the problem of determining if a path exists between two vertices in a directed graph, is an example of an important problem which is known to be complete for NL. In an intuitive sense, it is one of the "hardest" or "most expressive" problems in NL. Another important NL-complete problem is 2-satisfiability, which asks if, given a formula where each clause is the disjunction of two literals, is there a variable assignment which makes the formula true? An example instance, where ~ indicates not, might be:

Related Topics:
STConnectivity - Reachability - Directed graph - Complete - Satisfiability

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:(x1 or ~x3) and (~x2 or x3) and (~x1 or ~x2)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

It is known that NL is contained in P, since there is a polynomial-time algorithm for 2-satisfiability, but it is not known whether NL = P or whether L = NL. Since nondeterministic space is closed under complement, it is known that NL = co-NL, a celebrated result independently discovered by Neil Immerman and Róbert Szelepcsényi in 1987 (Immerman-Szelepcs%C3%A9nyi_Theorem) and awarded the 1995 Gödel Prize.

Related Topics:
P - Neil Immerman - Róbert Szelepcsényi - Immerman-Szelepcs%C3%A9nyi_Theorem - Gödel Prize

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

However, it is known that NL=RL, the class of problems solvable by probabilistic Turing machines in logarithmic space which incorrectly reject with probability < 1/3. It is also equal to ZPL, the class of problems solvable by randomized algorithms in log-space and expected polynomial time, with no error.

Related Topics:
RL - Probabilistic Turing machine - ZPL

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

There is a simple logical characterization of NL: it contains precisely those languages expressible in first order logic with an added transitive closure operator.

Related Topics:
First order logic - Transitive closure

~ ~ ~ ~ ~ ~ ~ ~ ~ ~