NL (complexity) - Containments

Containments

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. It is known that NL = co-NL, where co-NL is the class of languages whose complements are in NL. This result was independently discovered by Neil Immerman and Róbert Szelepcsényi in 1987 (Immerman-Szelepcsényi Theorem), who received the 1995 Gödel Prize for this work.

In circuit complexity, NL can be placed within the NC hierarchy. In Papadimitriou 1994, Theorem 16.1, we have:

More precisely, NL is contained in AC1. 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. It is not, however, known or believed to be equal to RLP or ZPLP, the polynomial-time restrictions of RL and ZPL which some authors refer to as RL and ZPL.

We can relate NL 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 as of 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). 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 PSPACE = NPSPACE.