查看“︁L (複雜度)”︁的源代码

{{unsolved|数学|<nowiki>L = P成立吗？</nowiki>}}
{{unsolved|数学|<nowiki>L = NL成立吗？</nowiki>}}
'''L'''也稱為'''LSPACE'''或'''DLOGSPACE'''，是[[计算复杂度理论]]中能被[[图灵机|确定型图灵机]]利用[[對數]]空间解决的[[判定问题]]集合。<ref name="sip295">{{harvtxt|Sipser|1997}}, Definition&nbsp;8.12, p.&nbsp;295.</ref><ref name="gj-177">{{harvtxt|Garey|Johnson|1979}}, p.&nbsp;177.</ref>

'''对数空间'''是指与输入规模成对数大小关系的可写的储存空间，大多数对数空间（'''LOGSPACE'''）算法以这种方式储存。<ref name="sip295"/>

重要的相關未解問題包括複雜度類L和P是否恆等（'''L = P'''）及複雜度類L和NL是否恆等（'''L = NL'''）。
目前已知有以下重要性质：
*'''L ⊆ NL ⊆ P'''
*'''NC<sup>1</sup> ⊆ L ⊆ NL ⊆ NC<sup>2</sup>'''<ref>{{cite book|last=Papadimitriou | first = C. | title= Computational Complexity |url=https://archive.org/details/computationalcom0000papa | publisher = Addison-Wesley | year = 1994
    | isbn = 0-201-53082-1 | chapter = Chapter 16: Logarithmic Space}}</ref>

== 相关复杂度类 ==
=== FL ===
和[[功能性問題]]相關的類別是FL，在[[计算复杂度理论]]，'''FL'''是一个复杂度类，是能被[[图灵机|确定型图灵机]]在对数空间下解决的[[函数问题]]的集合。<ref name="abj">{{citation|contribution=Functional oracle queries as a measure of parallel time|first1=Carme|last1=Àlvarez|first2=José L.|last2=Balcázar|first3=Birgit|last3=Jenner|title=STACS 91|series=Lecture Notes in Computer Science|volume=480|year=1991|pages=422–433|publisher=Springer|doi=10.1007/BFb0020817}}.</ref> 

依照同样的原理，可以定义相应的[[FP]]，[[FNP]]，[[TFNP]]。<ref name="abj"/>

FL常用来定义'''对数空间归约'''（Log-space reduction，Log-空间规约）。对数空间归约指仅使用对数空间的[[图灵机|确定型图灵机]]进行的规约。区别于常见的多项式时间规约，对数空间规约只允许DTM使用若干个log n（n是输入长度）空间。<ref name=AB88>Arora & Barak (2009) p. 88</ref>对数空间规约在定义'''NL-完全'''（'''NLC'''，'''NL-complete'''）问题时候起作用。
=== NL ===
'''L'''是[[NL (複雜度)|NL]]的子集，'''NL'''是可以被[[非確定型圖靈機]]利用對數空間解决的判定问题集合。利用[[薩維奇定理]]的建構式證明，可得證NL包含在复杂度[[P (複雜度)|P]]之內，也就是可以被確定型圖靈機在多項式空間解决的判定问题集合中。

存在几个已知的'''NL-完全'''问题，如{{link-en|2SAT|2-satisfiability}}。

根据[[萨维奇定理]]，我们已知有以下重要性质：
*<math>\mathrm{NL \subseteq SPACE}(\log^2 n) \ \ \ \  \text{equivalently, } \mathrm{NL \subseteq L}^2.</math> 
=== RL ===
在[[计算複杂度理论]]内，'''RL'''（Randomized Logarithmic-space，随机对数空间）<ref>{{CZoo|RL|R#rl}}</ref>，或者说'''RLP'''（Randomized Logarithmic-space Polynomial-time，随机对数空间多项式时间），<ref>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.</ref>是一个[[複杂度类]]，包含能以[[概率图灵机]]，在[[对数空间]]与[[多项式时间]]之内，在仅有[[单向容错]]的状况内解决的问题。此命名法与'''[[RP (复杂度)|RP]]'''，这个相近但是没有对数空间限制的複杂度类是雷同的。

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

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

我们也知道'''RL ⊆ NL'''裡面。另外'''RL ⊆ [[BPL (复杂度)|BPL]]'''内，这两个复杂度相似但是BPL允许双向容错（跟RL相比多出回答YES时可以犯错这部份）。显然地有'''RL ⊆ L'''，因为其定义比起L更一般化。Nisan于1992年证明了一个较弱的[[去随机化]]，推论出'''RL ⊆ [[SC (复杂度)|SC]]'''，<ref>N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.</ref>SC包含一般图灵机以多项式时间和多项式对数空间解决的问题；换句话说，给予一般机器多项式对数的空间，则可以模拟机率图灵机使用对数空间的能力。

一般相信'''RL = L'''，换句话说，概率图灵机不会在对数空间下比[[图灵机|确定型图灵机]]更强，多项式时间对数空间的计算方式可以完全的去随机化。这猜想的一个主要证据由Reingold et al.在2005年提出。<ref>O. Reingold and [[Luca Trevisan|L. Trevisan]] and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem, {{ECCC|2005|05|022}}, 2004.</ref>这问题的证明在无条件去随机化裡面可以说是一个被追寻的圣杯。这问题其中一个重大迈进是Omer Reingold证明了'''SL = L'''。

=== SL ===
在[[计算复杂度理论]]，'''SL'''（Symmetric Logspace，对称对数空间），是一个复杂度类，是能被{{link-en|对称图灵机|Symmetric Turing machine}}在[[L (复杂度)|对数空间]]下解决的[[判定问题]]的集合。<ref>{{citation
 | last1 = Lewis | first1 = Harry R. | author1-link = Harry R. Lewis
 | last2 = Papadimitriou | first2 = Christos H. | author2-link = Christos Papadimitriou
 | contribution = Symmetric space-bounded computation
 | doi = 10.1007/3-540-10003-2_85
 | location = Berlin
 | mr = 589018
 | pages = 374–384
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Proceedings of the Seventh International Colloquium on Automata, Languages and Programming
 | volume = 85
 | year = 1980}}</ref>其存在以下重要性质：<br>
*'''L'''&nbsp;⊆&nbsp;'''SL'''&nbsp;⊆&nbsp;'''NL'''
*'''SL''' = co-'''SL'''
**并直接导致'''L'''<sup>'''SL'''</sup> = '''SL'''<ref name="#1">{{citation
 | last1 = Nisan | first1 = Noam | author1-link = Noam Nisan
 | last2 = Ta-Shma | first2 = Amnon
 | id = {{ECCC|1994|94|003}}
 | journal = Chicago Journal of Theoretical Computer Science
 | mr = 1345937
 | at = Article 1
 | title = Symmetric logspace is closed under complement
 | year = 1995}}</ref>

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

2004年10月Omer Reingold成功证明USTCON问题属于L，因为USTCON问题属于SL完全，这便等于证明了'''SL = L'''。即，SL是L的一种变体。<ref name="#1"/>

== 参考资料 ==
{{Reflist|}}
{{复杂度类}}

[[Category:复杂度类]]
[[Category:機率複雜度類]]
[[Category:闭包算子]]
[[Category:计算机科学中未解决的问题]]