PROFILPELAJAR.COM

未解決的数学問題：L = P成立吗？

未解決的数学問題：L = NL成立吗？

L也稱為LSPACE或DLOGSPACE，是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。^[1]^[2]

对数空间是指与输入规模成对数大小关系的可写的储存空间，大多数对数空间（LOGSPACE）算法以这种方式储存。^[1]

重要的相關未解問題包括複雜度類L和P是否恆等（L = P）及複雜度類L和NL是否恆等（L = NL）。目前已知有以下重要性质：

L ⊆ NL ⊆ P
NC¹ ⊆ L ⊆ NL ⊆ NC²^[3]

相关复杂度类

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）。

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

$\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]

参考资料

^ ^1.0 ^1.1 Sipser (1997), Definition 8.12, p. 295.
^ Garey & Johnson (1979), p. 177.
^ Papadimitriou, C. Chapter 16: Logarithmic Space. Computational Complexity. Addison-Wesley. 1994. ISBN 0-201-53082-1.
^ ^4.0 ^4.1 Àlvarez, Carme; Balcázar, José L.; Jenner, Birgit, Functional oracle queries as a measure of parallel time, STACS 91, Lecture Notes in Computer Science 480, Springer: 422–433, 1991, doi:10.1007/BFb0020817 .
^ Arora & Barak (2009) p. 88
^ Complexity Zoo: RL
^ A. Borodin, S.A. Cook, P.W. Dymond, W.L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(3):559–578. 1989.
^ N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.
^ O. Reingold and L. Trevisan and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem, Template:ECCC, 2004.
^ Lewis, Harry R.; Papadimitriou, Christos H., Symmetric space-bounded computation, Proceedings of the Seventh International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 85, Berlin: Springer: 374–384, 1980, MR 0589018, doi:10.1007/3-540-10003-2_85
^ ^11.0 ^11.1 Nisan, Noam; Ta-Shma, Amnon, Symmetric logspace is closed under complement, Chicago Journal of Theoretical Computer Science, 1995, Article 1, MR 1345937, Template:ECCC