檢視 L(複雜度) 的原始碼

'''L'''嘛叫做'''LSPACE'''抑是'''DLOGSPACE'''，是計算複雜度理論中會當予確定型圖靈機利用對數空間解決的判定問題集合。

'''嘿數空間'''是講佮輸入規模成對數大細關係的可寫的儲存空間，大多數對數空間（'''LOGSPACE'''）算法用這種方式儉存。

重要的相關無解問題包括複雜度類 L 和 P 敢是恆等（'''L=P'''）佮複雜度類 L 和 NL 敢是恆等（'''L=NL'''）。
目前已經知有以下重要性質：

*'''L ⊆ NL ⊆ P'''
*'''NC 一 ⊆ L ⊆ NL ⊆ NC 二'''

==相關複雜度類==

===FL===

和功能性問題相關的類別是 FL，佇咧算複雜度理論，'''FL'''是一个複雜度類，是會當予人確定型圖靈機佇咧對數空間下解決的函數問題的集合。

照仝款的原理，會當定義相應的 FP，FNP，TFNP。

FL 定定用來定義'''著數空間歸約'''（Log-space reduction，Log-空間規約）。 對數空間歸約指干焦使用對數空間確定型圖靈機來進行的規約。區別捷看的多項式時間規約，嘿數空間規約只允准 DTM 使用如果干個 log n（n 是輸入長度）空間。嘿數空間規約佇定義'''NL-完全'''（'''NLC'''，'''NL-complete'''）問題的時陣你起作用。

===NL===

'''L'''是 NL 的子集，'''NL'''是會當予非確定型圖靈機利用對數空間解決的判定問題集合。利用薩維奇定理的建構式證明，會當證 NL 包括咧複雜度 P 之內，也就是會當予確定型圖靈機佇多項式空間解決的判定問題集合中。

存在幾个已知的'''NL-完全'''問題，如二 SAT。

根據薩維奇定理，咱已經知影有以下重要性質：

* $ \ mathrm { NL \ subseteq SPACE } ( \ log ^ { 二 } n ) \ \ \ \ { \ text { equivalently , } } \ mathrm { NL \ subseteq L } ^ { 二 } . $

===RL===

佇咧算複雜度理論內，'''RL'''（Randomized Logarithmic-space，隨機對數空間）， 抑是講'''RLP'''（Randomized Logarithmic-space Polynomial-time，隨機對數空間多項式時間）， 是一个複雜度類，包含講會當概率圖靈機，佇對數空間佮多項式時間之內，佇只有單向容毋著的狀況內解決的問題。這號名法佮'''RP'''，這相倚但是無對數空間的限制的複雜度類是雷同的。

佇定義'''RL'''的概率圖靈機，袂曉咧應 YES 的時陣犯錯。但是允准咧回答講 NO 的時陣有小於三分之一的犯錯機會；這種容納錯誤的方式予人號做 _ 單向容毋著 _（one-sided error）。 遮的三分之一毋是一个絕對的數值；任何 _ x _ 符合 [ 零 , 二分之一 ) 內攏會使。因為咱會當透過重複執行規个演算法將犯錯率壓縮到二 ? _ p _ ( _ x _ ) 倍小（_ p _ ( _ x _ ) 代表 x 的任意多項式）， 毋開超過真濟項式時間抑是對數空間資源。

有時'''RL'''這个名稱使用佇咧使用對數空間無限時間通解決的問題其複雜度類。毋過，根據 Immerman–Szelepcsényi 定理，欲述這个類別會當使用概率計數器證明'''RL'=NL'''，所以一般直接使用'''NL'''來代表講。

咱嘛知影'''RL ⊆ NL'''內底。另外咧'''RL ⊆ BPL'''內，這兩个複雜度相𫝛但是 BPL 允准雙向容錯（佮 RL 相比出來講 YES 時會當犯錯這个部份）。 顯然來講'''RL ⊆ L'''，因為其定義比起來 L 閣較一般化。Nisan 佇一九九二年證明一个較弱的去隨機化，推論出'''RL ⊆ SC'''，SC 包含一般圖靈機以多項式時間佮多項式對數空間解決的問題；嘛會使講，予一般機器多項對數的空間，是會當模擬機率圖靈機使用對數空間的能力。

一般相信'''RL=L'''，嘛會使講，概率圖靈機袂佇咧對數空間下比確定型圖靈機閣較強，多項式時間對數空間的計算方式會當完全的去隨機化。這猜想的一个主要證據由 Reingold et al . 佇二空空五年提出。這个問題的證明佇咧無條件去隨機化內底會當講是一个予人追尋的象桮。這問題其中一个重大邁進是 Omer Reingold 證明矣'''SL=L'''。

===SL===

佇咧算複雜度理論，'''SL'''（Symmetric Logspace，對稱對數空間）， 是一个複雜度類，是會當予對稱圖靈機佇對數空間解決的判定問題的集合。其存在以下重要性質：

*'''L''' ⊆ '''SL''' ⊆ '''NL'''
*'''SL'''=co-'''SL'''
* 並直接造成'''L''''''SL'''='''SL'''

USTCON 問題（undirected s-t connectivity，關於無向圖兩點之間是毋是存在一个路徑的問題）做為一个'''SL 完全'''（'''SLC'''，'''SL-complete'''）的 SL 下的重要特例，通常佮 SL 本身予人討論。

二空空四年十月 Omer Reingold 成功證明 USTCON 問題屬於 L，因為乎 USTCON 問題屬於 SL 完全，這便等於證明矣'''SL=L'''。即，SL 是 L 的一種變體。

==參考資料==

[[分類: 待校正]]