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 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:
Containments
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 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. In Papadimitriou 1994, Theorem 16.1, we have: More precisely, is contained in. It is known that is equal to, the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to or, the polynomial-time restrictions of and which some authors refer to as and. We can relate to deterministic space using Savitch's theorem, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that: This was the strongest deterministic-space inclusion known in 1994. Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have.
Alternative definitions
Probabilistic definition
Suppose C is the complexity class of decision problems solvable in logarithmithic space with probabilistic Turing machines that never accept incorrectly but are allowed to reject incorrectly less than 1/3 of the time; this is called one-sided error. The constant 1/3 is arbitrary; any x with 0 ≤ x < 1/2 would suffice. It turns out that C = NL. Notice that C, unlike its deterministic counterpart L, is not limited to polynomial time, because although it has a polynomial number of configurations it can use randomness to escape an infinite loop. If we do limit it to polynomial time, we get the class RL, which is contained in but not known or believed to equal NL. There is a simple algorithm which establishes that C = NL. Clearly C is contained in NL, since:
If the string is not in the language, both reject along all computation paths.
If the string is in the language, an NL algorithm accepts along at least one computation path and a C algorithm accepts along at least two-thirds of its computation paths.
To show that NL is contained in C, we simply take an NL algorithm and choose a random computation path of length n, and do this 2n times. Because no computation path exceeds length n, and because there are 2n computation paths in all, we have a good chance of hitting the accepting one. The only problem is that we don't have room in log space for a binary counter that goes up to 2n. To get around this we replace it with a randomized counter, which simply flips n coins and stops and rejects if they all land on heads. Since this event has probability 2−n, we expect to take 2n steps on average before stopping. It only needs to keep a running total of the number of heads in a row it sees, which it can count in log space. Because of the Immerman–Szelepcsényi theorem, according to which NL is closed under complements, the one-sided error in these probabilistic computations can be replaced by zero-sided error. That is, these problems can be solved by probabilistic Turing machines that use logarithmic space and never make errors. The corresponding complexity class that also requires the machine to use only polynomial time is called ZPLP. Thus, when we only look at space alone, it seems that randomization and nondeterminism are equally powerful.
Certificate definition
NL can equivalently be characterised by certificates, analogous to classes such as NP. Consider a deterministic logarithmic-space bounded Turing machine that has an additional read-only read-once input tape. A language is in NLif and only if such a Turing machine accepts any word in the language for an appropriate choice of certificate in its additional input tape, and rejects any word not in the language regardless of the certificate.
Descriptive complexity
There is a simple logical characterization of NL: it contains precisely those languages expressible in first-order logic with an added transitive closure operator.
Closure properties
The class NL is closed under the operations complementation, union, and therefore intersection, concatenation, and Kleene star.
