L (複雜度)

FL

和功能性问题相关的类别是FL，在计算复杂度理论，FL是一个复杂度类，是能被确定型图灵机在对数空间下解决的函数问题的集合。
依照同样的原理，可以定义相应的FP，FNP，TFNP。
FL常用来定义对数空间归约（Log-space reduction，Log-空间规约）。对数空间归约指仅使用对数空间的确定型图灵机进行的规约。区别于常见的多项式时间规约，对数空间规约只允许DTM使用若干个log n（n是输入长度）空间。对数空间规约在定义NL-完全（NLC，NL-complete）问题时候起作用。

RL

在计算复杂度理论内，RL（Randomized Logarithmic-space，随机对数空间），或者说RLP（Randomized Logarithmic-space Polynomial-time，随机对数空间多项式时间），是一个复杂度类，包含能以概率图灵机，在对数空间与多项式时间之内，在仅有单向容错的状况内解决的问题。此命名法与RP，这个相近但是没有对数空间限制的复杂度类是雷同的。
在定义RL时的概率图灵机，不会在回答YES的时候犯错。但是允许在回答NO的时候有小于1/3的犯错机会；这种容纳错误的方式被称作单向容错（one-sided error）。这里的1/3不是一个绝对的数值；任何x符合[0,1/2)内都可以。因为我们可以借由重复执行整个算法将犯错率压缩到2倍小（p(x)代表x的任意多项式），而不花费超过多项式时间或者对数空间的资源。
有时RL这个名称使用于使用对数空间不限时间能解决的问题其复杂度类。然而，根据Immerman–Szelepcsényi定理，上述这个类别可以使用概率计数器证明RL' = NL，因此一般直接使用NL来代表。
我们也知道RL ⊆ NL里面。另外RL ⊆ BPL内，这两个复杂度相似但是BPL允许双向容错（跟RL相比多出回答YES时可以犯错这部分）。显然地有RL ⊆ L，因为其定义比起L更一般化。Nisan于1992年证明了一个较弱的去随机化，推论出RL ⊆ SC，SC包含一般图灵机以多项式时间和多项式对数空间解决的问题；换句话说，给予一般机器多项式对数的空间，则可以模拟机率图灵机使用对数空间的能力。
一般相信RL = L，换句话说，概率图灵机不会在对数空间下比确定型图灵机更强，多项式时间对数空间的计算方式可以完全的去随机化。这猜想的一个主要证据由Reingold et al.在2005年提出。这问题的证明在无条件去随机化里面可以说是一个被追寻的圣杯。这问题其中一个重大迈进是Omer Reingold证明了SL = L。