Editing L (complexity) (section)

== Random versions ==
Just as how '''P''' has several random versions: '''[[BPP (complexity)|BPP]]''', '''[[ZPP (complexity)|ZPP]]''', '''[[PP (complexity)|PP]]''', and '''[[RP (complexity)|RP]]''', there are several random versions of '''L'''.

'''Bounded-error Probability L''' ('''BPL''') is defined like '''BPP''', as the complexity class of problems solvable with a logspace Turing machine such that:

* Other than the usual tapes of a logspace Turing machine, the machine also takes a tape filled with random bits.
* The randomness is read-only and one-way. That is, the read-head on the random tape can only move in one direction. To reference a previous random bit, the machine must store it in the work tape.
* The Turing machine has to halt for every input and every random tape.
* If the answer is 'yes' then the machine accepts with probability at least 2/3. If the answer is 'no' then the machine rejects with probability at least 2/3.

It is contained in '''NC'''<sup>''2''</sup>, which is contained in '''P'''.<ref>{{Cite journal |last1=Borodin |first1=A. |last2=Cook |first2=S. |last3=Pippenger |first3=N. |date=1983-07-01 |title=Parallel computation for well-endowed rings and space-bounded probabilistic machines |url=https://www.sciencedirect.com/science/article/pii/S0019995883800606 |journal=Information and Control |volume=58 |issue=1 |pages=113–136 |doi=10.1016/S0019-9958(83)80060-6 |issn=0019-9958}}</ref>

'''BP•L''' is defined the same as '''BPL''', except that the machine is allowed to read the random tape both forwards and backwards. It contains '''BPL'''. It is also exactly equal to the class of languages that are nearly logspace: a language is nearly logspace if, [[Oracle machine|relative]] to almost every oracle, the language is in '''L'''.<ref name=":0" />

'''ZP•L''' is defined like '''BP•L''', except that the machine may output "unknown", and must never make an error (i.e. accept when the answer is 'no', and vice versa). The relation of '''ZP•L''' to '''BP•L''', is the same as the relation of [[ZPP (complexity)|'''ZPP''']] to [[BPP (complexity)|'''BPP''']]. It contains '''BPL''' and is contained by '''BP•L'''.<ref name=":0">{{Cite journal |last=Nisan |first=Noam |date=1993-01-04 |title=On read once vs. multiple access to randomness in logspace |url=https://dx.doi.org/10.1016/0304-3975%2893%2990258-U |journal=Theoretical Computer Science |volume=107 |issue=1 |pages=135–144 |doi=10.1016/0304-3975(93)90258-U |issn=0304-3975}}</ref>

'''Randomized L''' ('''RL''') is defined like '''BPL''':

* Other than the usual tapes of a logspace Turing machine, the machine also takes a read-only one-way tape filled with random bits.
* The Turing machine has to halt for every input and every random tape.
* If the answer is 'yes,' accept with probability at least 1/2.
* If the answer is 'no,' always reject.

Also, it must always run in polynomial time (since otherwise we would just get '''[[NL (complexity)|NL]]'''). It is strongly suspected that '''RL''' = '''L'''.<ref>{{Cite book |last1=Reingold |first1=Omer |last2=Trevisan |first2=Luca |last3=Vadhan |first3=Salil |chapter=Pseudorandom walks on regular digraphs and the RL vs. L problem |date=2006-05-21 |title=Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing |chapter-url=https://dl.acm.org/doi/10.1145/1132516.1132583 |series=STOC '06 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=457–466 |doi=10.1145/1132516.1132583 |isbn=978-1-59593-134-4}}</ref>

Both '''BPL''' and '''RL''' are contained in [[Steve's Class]].<ref>{{Cite journal |last=Nisan |first=Noam |date=1994-03-01 |title=RL ⊆ SC |url=https://link.springer.com/article/10.1007/BF01205052 |journal=Computational Complexity |language=en |volume=4 |issue=1 |pages=1–11 |doi=10.1007/BF01205052 |issn=1420-8954}}</ref>

'''Probabilistic L''' ('''PL''') has the same relation to '''L''' that '''[[PP (complexity)|PP]]''' has to '''P''': 

* If the answer is 'yes,' accept with probability at least 1/2.
* If the answer is 'no,' reject with probability at least 1/2.
It contains '''BPL''', and is contained by '''NC'''<sup>''2''</sup>.<ref>{{Cite journal |last=Cook |first=Stephen A. |date=1985-01-01 |title=A taxonomy of problems with fast parallel algorithms |url=https://www.sciencedirect.com/science/article/pii/S0019995885800413 |journal=Information and Control |series=International Conference on Foundations of Computation Theory |volume=64 |issue=1 |pages=2–22 |doi=10.1016/S0019-9958(85)80041-3 |issn=0019-9958}}</ref>