基本介紹
- 中文名：複雜度
- 外文名：LSPACE
- 別稱：DLOGSPACE
- 學科：計算機
- 領域：計算機
- 作用：解決的判定問題集合
簡介,相關複雜度類,FL,NL,RL,SL,
簡介
對數空間是指與輸入規模成對數大小關係的可寫的儲存空間，大多數對數空間（LOGSPACE）算法以這種方式儲存。
重要的相關未解問題包括複雜度類L和P是否恆等（L = P）及複雜度類L和NL是否恆等（L = NL）。 目前已知有以下重要性質：
- L ⊆ NL ⊆ P
- NC1 ⊆ L ⊆ NL ⊆ NC2
相關複雜度類
FL
依照同樣的原理，可以定義相應的FP，FNP，TFNP。
FL常用來定義對數空間歸約（Log-space reduction，Log-空間規約）。對數空間歸約指僅使用對數空間的確定型圖靈機進行的規約。區別於常見的多項式時間規約，對數空間規約只允許DTM使用若干個log n（n是輸入長度）空間。對數空間規約在定義NL-完全（NLC，NL-complete）問題時候起作用。
NL
存在幾個已知的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的一種變體。
