Editing NL (complexity) (section)

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