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 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. NL can be formally defined in terms of the computational resource nondeterministic space (or NSPACE) as NL = NSPACE(log n). Important results in complexity theory allow us to relate this complexity class with other classes, telling us about the relative power of the resources involved. Results in the field of algorithms, on the other hand, tell us which problems can be solved with this resource. Like much of complexity theory, many important questions about NL are still open (see Unsolved problems in computer science). Occasionally NL is referred to as RL due to its probabilistic definition below; however, this name is more frequently used to refer to randomized logarithmic space, which is not known to equal NL. Several problems are known to be NL-complete under log-space reductions, including ST-connectivity and 2-satisfiability. ST-connectivity asks, for nodes S and T in a directed graph, whether T is reachable from S. 2-satisfiability asks, given a propositional formula of which each clause is the disjunction of two literals, if there is a variable assignment that makes the formula true. An example instance, where indicates not, might be: It is known that is contained in , since there is a polynomial-time algorithm for 2-satisfiability, but it is not known whether or whether . It is known that , where is the class of languages whose complements are in . This result (the Immerman–Szelepcsényi theorem) was independently discovered by Neil Immerman and Róbert Szelepcsényi in 1987; they received the 1995 Gödel Prize for this work. In circuit complexity, can be placed within the hierarchy.