RL (複雜度)

维基百科,自由的百科全书
跳转至: 导航搜索

計算複雜度理論內,RL(Randomized Logarithmic-space,隨機對數空間),[1]或者又叫做RLP(Randomized Logarithmic-space Polynomial-time,隨機對數空間多項式時間),[2]是一個複雜度類,包含能以概率圖靈機,在對數空間多項式時間之內,在僅有單向容錯的狀況內解決的問題。此命名法與RP,這個相近但是沒有對數空間限制的複雜度類是雷同的。

在定義RL時的概率圖靈機,不會在回答YES的時候犯錯。但是允許在回答NO的時候有小於1/3的犯錯機會;這種容納錯誤的方式被稱作單向容錯(one-sided error)。這裡的1/3不是一個絕對的數值;任何x符合 0 ≤ x < 1/2 都可以。因為我們可以藉由重複執行整個演算法將犯錯率壓縮到 2p(x)倍小(p(x)代表x的任意多項式),而不花費超過多項式時間或者對數空間的資源。

有時RL這個名稱使用於使用對數空間不限時間能解決的問題其複雜度類。然而,上述這個類別可以使用概率計數器證明與NL是相同的,因此一般直接使用NL來代表;我們也知道RL包含於NL裡面。 另外RL包含於BPL內,這兩個複雜度相似但是BPL允許雙向容錯(跟RL相比多出回答YES時可以犯錯這部份)。RL 包含了L(一般的圖靈機使用對數空間能解決的問題),因為其定義比起L更一般化。 Nisan於1992年證明了一個較弱的去隨機化,推論出RL包含在SC裡面,[3]SC包含一般圖靈機以多項式時間和多項式對數空間解決的問題;換句話說,給予一般機器多項式對數的空間,則可以模擬機率圖靈機使用對數空間的能力。

一般相信RL等於L,換句話說,多項式時間對數空間的計算方式可以完全的去隨機化。這猜想的一個主要證據由Reingold et al.在2005年提出。[4] 這問題的證明在無條件去隨機化裡面可以說是一個被追尋的聖杯。這問題其中一個重大邁進是Omer Reingold證明了SL等於L

參考資料[编辑]

  1. ^ Complexity Zoo: RL
  2. ^ 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.
  3. ^ N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.
  4. ^ O. Reingold and L. Trevisan and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem, Template:ECCC, 2004.