Editing NL (complexity) (section)

{{Short description|Computational complexity}}
{{unsolved|computer science|{{tmath|\mathsf{L \overset?{{=}} NL} }}}}
In [[computational complexity theory]], '''NL''' ('''N'''ondeterministic '''L'''ogarithmic-space) is the [[complexity class]] containing [[decision problem]]s that can be solved by a [[nondeterministic Turing machine]] using a [[logarithm]]ic amount of [[Memory space (computational resource)|memory space]].

'''NL''' is a generalization of '''[[L (complexity)|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'''.

'''NL''' can be formally defined in terms of the computational resource [[nondeterministic space]] (or NSPACE) as '''NL''' = '''NSPACE'''(log ''n'').

Important results in complexity theory allow us to relate this complexity class with other classes, telling us about the relative power of the resources involved.  Results in the field of [[algorithm]]s, on the other hand, tell us which problems can be solved with this resource.  Like much of complexity theory, many important questions about '''NL''' are still [[open problem|open]] (see [[Unsolved problems in computer science]]).

Occasionally '''NL''' is referred to as '''RL''' due to its [[#Probabilistic definition|probabilistic definition]] below; however, this name is more frequently used to refer to [[RL (complexity)|randomized logarithmic space]], which is not known to equal '''NL'''.