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.

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.

STConnectivity , 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:

(x₁ or ~x₃) and (~x₂ or x₃) and (~x₁ or ~x₂)

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.

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.

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

References

C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0201530821. Chapter 16: Logarithmic Space.