Editing NL (complexity) (section)

==Definitions==
There are several equivalent definitions of the '''NL''' class.

=== 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.

===Probabilistic definition===
Suppose ''C'' is the [[complexity class]] of [[decision problems]] solvable in logarithmithic space with [[probabilistic Turing machine]]s that never accept incorrectly but are allowed to reject incorrectly less than 1/3 of the time; this is called ''one-sided error''. The constant 1/3 is arbitrary; any ''x'' with 0 ≤ ''x'' < 1/2 would suffice.

It turns out that ''C'' = '''NL'''. Notice that ''C'', unlike its deterministic counterpart '''[[L (complexity)|L]]''', is not limited to polynomial time, because although it has a polynomial number of configurations it can use randomness to escape an infinite loop. If we do limit it to polynomial time, we get the class '''[[RL (complexity)|RL]]''', which is contained in but not known or believed to equal '''NL'''.

There is a simple algorithm that establishes that ''C'' = '''NL'''. Clearly ''C'' is contained in '''NL''', since:
* If the string is not in the language, both reject along all computation paths.
* If the string is in the language, an '''NL''' algorithm accepts along at least one computation path and a ''C'' algorithm accepts along at least two-thirds of its computation paths.
To show that '''NL''' is contained in ''C'', we simply take an '''NL''' algorithm and choose a random computation path of length ''n'', and execute this 2<sup>''n''</sup> times. Because no computation path exceeds length ''n'', and because there are 2<sup>''n''</sup> computation paths in all, we have a good chance of hitting the accepting one (bounded below by a constant).

The only problem is that we don't have room in log space for a binary counter that goes up to 2<sup>''n''</sup>. 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. Since this event has probability 2<sup>−''n''</sup>, we [[expected value|expect]] to take 2<sup>''n''</sup> steps on average before stopping. It only needs to keep a running total of the number of heads in a row it sees, which it can count in log space.

Because of the [[Immerman–Szelepcsényi theorem]], according to which NL is closed under complements, the one-sided error in these probabilistic computations can be replaced by zero-sided error. That is, these problems can be solved by probabilistic Turing machines that use logarithmic space and never make errors. The corresponding complexity class that also requires the machine to use only polynomial time is called [[ZPLP (complexity)|ZPLP]].

Thus, when we only look at space, it seems that randomization and nondeterminism are equally powerful.

===Certificate definition===
'''NL''' can equivalently be characterised by [[Certificate (complexity)|certificates]], analogous to classes such as '''[[NP (complexity)|NP]]'''. Let a ''verifier'' be a deterministic logarithmic-space bounded deterministic Turing machine that has an additional read-only read-once input tape (that is, the verifier may only move the read-head forwards, never backwards).

A language <math>L</math> is in '''NL''' if and only if<ref name=":0">{{cite book |last1=Arora |first1=Sanjeev |url=http://www.cs.princeton.edu/theory/complexity/ |title=Complexity Theory: A Modern Approach |last2=Barak |first2=Boaz |date=2009 |publisher=Cambridge University Press |isbn=978-0-521-42426-4 |chapter= |author1link=Sanjeev Arora |author2link=Boaz Barak}}</ref>{{Pg|location=Definition 4.19}} 

* There exists a polynomial function <math>p</math>.
* There exists a verifier <math>TM</math>.
* For any <math>x</math>, <math>x \in L</math> iff there exists a certificate <math>u</math> with length <math>|u| \leq p(|x|)</math>, such that <math>TM(x, u) = 1</math>.

In words, it means that if a sentence is in the language, then there exists a polynomial-length proof that it is in the language. It does not say anything about the case where the sentence is ''not'' in the language, though by the Immerman–Szelepcsényi theorem, it is clear that there exists some verifier that can verify both <math>x \in L</math> and <math>x \not\in L</math>.

Note that the read-once condition is necessary. If the verifier can read forwards and backwards, this extends the class to the '''NP''' class.<ref name=":0" />{{Pg|location=Exercise 4.7}}

[[Cem Say]] and Abuzer Yakaryılmaz have proven that the deterministic logarithmic-space Turing machine in the statement above can be replaced by a bounded-error probabilistic constant-space Turing machine that is allowed to use only a constant number of random bits.<ref>A. C. Cem Say, Abuzer Yakaryılmaz, "Finite state verifiers with constant randomness," ''Logical Methods in Computer Science'', Vol. 10(3:6)2014, pp. 1-17.</ref>

=== Descriptive definition ===
In [[descriptive complexity theory]], '''NL''' is defined as those languages expressible in [[first-order logic]] with an added [[transitive closure]] operator.