L (复杂度)

FL

和功能性问题相关的类别是FL，在计算复杂度理论，FL是一个复杂度类，是能被确定型图灵机在对数空间下解决的函数问题的集合。^[4]

依照同样的原理，可以定义相应的FP，FNP，TFNP。^[4]

FL常用来定义对数空间归约（Log-space reduction，Log-空间规约）。对数空间归约指仅使用对数空间的确定型图灵机进行的规约。区别于常见的多项式时间规约，对数空间规约只允许DTM使用若干个log n（n是输入长度）空间。^[5]对数空间规约在定义NL-完全（NLC，NL-complete）问题时候起作用。

NL

L是NL的子集，NL是可以被非确定型图灵机利用对数空间解决的判定问题集合。利用萨维奇定理的建构式证明，可得证NL包含在复杂度P之内，也就是可以被确定型图灵机在多项式空间解决的判定问题集合中。

存在几个已知的NL-完全问题，如2SAT（英语：2-satisfiability）。

根据萨维奇定理，我们已知有以下重要性质：

• ${\displaystyle \mathrm {NL\subseteq SPACE} (\log ^{2}n)\ \ \ \ {\text{equivalently, }}\mathrm {NL\subseteq L} ^{2}.}$ 

RL

在计算复杂度理论内，RL（Randomized Logarithmic-space，随机对数空间）^[6]，或者说RLP（Randomized Logarithmic-space Polynomial-time，随机对数空间多项式时间），^[7]是一个复杂度类，包含能以概率图灵机，在对数空间与多项式时间之内，在仅有单向容错的状况内解决的问题。此命名法与RP，这个相近但是没有对数空间限制的复杂度类是雷同的。

在定义RL时的概率图灵机，不会在回答YES的时候犯错。但是允许在回答NO的时候有小于1/3的犯错机会；这种容纳错误的方式被称作单向容错（one-sided error）。这里的1/3不是一个绝对的数值；任何x符合[0,1/2)内都可以。因为我们可以借由重复执行整个算法将犯错率压缩到2^?p(x)倍小（p(x)代表x的任意多项式），而不花费超过多项式时间或者对数空间的资源。

有时RL这个名称使用于使用对数空间不限时间能解决的问题其复杂度类。然而，根据Immerman–Szelepcsényi定理（英语：Immerman–Szelepcsényi theorem），上述这个类别可以使用概率计数器证明RL' = NL，因此一般直接使用NL来代表。

我们也知道RL ⊆ NL里面。另外RL ⊆ BPL内，这两个复杂度相似但是BPL允许双向容错（跟RL相比多出回答YES时可以犯错这部分）。显然地有RL ⊆ L，因为其定义比起L更一般化。Nisan于1992年证明了一个较弱的去随机化，推论出RL ⊆ SC，^[8]SC包含一般图灵机以多项式时间和多项式对数空间解决的问题；换句话说，给予一般机器多项式对数的空间，则可以模拟机率图灵机使用对数空间的能力。

一般相信RL = L，换句话说，概率图灵机不会在对数空间下比确定型图灵机更强，多项式时间对数空间的计算方式可以完全的去随机化。这猜想的一个主要证据由Reingold et al.在2005年提出。^[9]这问题的证明在无条件去随机化里面可以说是一个被追寻的圣杯。这问题其中一个重大迈进是Omer Reingold证明了SL = L。

SL

在计算复杂度理论，SL（Symmetric Logspace，对称对数空间），是一个复杂度类，是能被对称图灵机（英语：Symmetric Turing machine）在对数空间下解决的判定问题的集合。^[10]其存在以下重要性质：

• L ⊆ SL ⊆ NL
• SL = co-SL
  • 并直接导致L^SL = SL^[11]

USTCON问题（undirected s-t connectivity，关于无向图两点之间是否存在一个路径的问题）作为一个SL完全（SLC，SL-complete）的SL下的重要特例，通常和SL本身被一起讨论。

2004年10月Omer Reingold成功证明USTCON问题属于L，因为USTCON问题属于SL完全，这便等于证明了SL = L。即，SL是L的一种变体。^[11]