Editing NL (complexity) (section)

==Containments==
It is known that {{sans-serif|NL}} is contained in {{sans-serif|[[P (complexity)|P]]}}, since there is a [[polynomial-time algorithm]] for [[2-satisfiability]], but it is not known whether {{sans-serif|NL {{=}} P}} or whether {{sans-serif|L {{=}} NL}}. It is known that {{sans-serif|NL {{=}} co-NL}}, where {{sans-serif|co-NL}} is the class of languages whose [[complement (complexity)|complement]]s are in {{sans-serif|NL}}. 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]], {{sans-serif|NL}} can be placed within the {{sans-serif|[[NC (complexity)|NC]]}} hierarchy.  In Papadimitriou 1994, Theorem 16.1, we have:

:<math>\mathsf{NC_1 \subseteq L \subseteq NL \subseteq NC_2}</math>.

More precisely, {{sans-serif|NL}} is contained in {{sans-serif|[[AC (complexity)|AC<sup>1</sup>]]}}. It is known that {{sans-serif|NL}} is equal to {{sans-serif|[[ZPL (complexity)|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 {{sans-serif|[[RLP (complexity)|RLP]]}} or {{sans-serif|[[ZPLP (complexity)|ZPLP]]}}, the polynomial-time restrictions of {{sans-serif|RL}} and {{sans-serif|ZPL}}, which some authors refer to as {{sans-serif|RL}} and {{sans-serif|ZPL}}.

We can relate {{sans-serif|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:

:<math>\mathsf{NL \subseteq SPACE}(\log^2 n) \ \ \ \  \text{equivalently, } \mathsf{NL \subseteq L}^2.</math>

This was the strongest deterministic-space inclusion known in 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 {{sans-serif|[[PSPACE]] {{=}} [[NPSPACE]]}}.