LSPACE

L也稱為LSPACE或DLOGSPACE，是計算複雜度理論中能被確定型圖靈機利用對數空間解決的判定問題集合。

基本介紹

• 中文名：複雜度
• 外文名：LSPACE
• 別名：DLOGSPACE
• 學科：計算機
• 領域：計算機
• 作用：解決的判定問題集合

簡介

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-完全問題，如2SAT。

根據薩維奇定理，我們已知有以下重要性質：

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。

SL

在計算複雜度理論，SL（Symmetric Logspace，對稱對數空間），是一個複雜度類，是能被對稱圖靈機在對數空間下解決的判定問題的集合。其存在以下重要性質：

• L⊆SL⊆NL
• SL= co-SL
• 並直接導致L=SL

USTCON問題（undirected s-t connectivity，關於無向圖兩點之間是否存在一個路徑的問題）作為一個SL完全（SLC，SL-complete）的SL下的重要特例，通常和SL本身被一起討論。

2004年10月Omer Reingold成功證明USTCON問題屬於L，因為USTCON問題屬於SL完全，這便等於證明了SL = L。即，SL是L的一種變體。