Like much of complexity theory, many important questions about NL are still open (see Unsolved problems in computer science).
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.
It is known that NL is equal to ZPL, the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error.
From Savitch's theorem, we have directly that: This was the strongest deterministic-space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space").
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.
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.
That is, these problems can be solved by probabilistic Turing machines that use logarithmic space and never make errors.
Consider a deterministic logarithmic-space bounded Turing machine that has an additional read-only read-once input tape.
The class NL is closed under the operations complementation, union, and therefore intersection, concatenation, and Kleene star.