Home > 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.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:
- (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.
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 ZPLThis article is about the complexity class. For the programming language, see ZPL programming language. In complexity theory, ZPL (Zero-error Probabilistic Logarithmic space) is the set of problems solvable by a probabilistic Turing machine which always y, 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 closureIn mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R''. For any relation R the transitive closure of R always exits. To see this note that the intersection of any family of trans operator.
References
C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. BooksEnthsiast.com. Chapter 16: Logarithmic Space.
complexity classes
