Editing NL (complexity) (section)

=== Standard definition ===
'''NL''' is the complexity class of decision problems that can be solved by a nondeterministic Turing machine (NTM) using a logarithmic amount of memory space.

In more detail, a language <math>L</math> is NL iff there exists a NTM <math>M</math> such that 

* <math>M</math> runs on logspace.
* <math>M</math> always halts.

* If <math>x \in L</math>, then there exists at least one computational trace of <math>M(x)</math> that results in the machine halting in an accepting state.
* If <math>x \not\in L</math>, then all computational traces of <math>M(x)</math> results in the machine halting in an unaccepting state.