^Borodin, A.; Cook, S. A.; Dymond, P. W.; Ruzzo, W. L.; Tompa, M., Two applications of inductive counting for complementation problems, SIAM Journal on Computing, 1989, 18 (3): 559–578, doi:10.1137/0218038.
^Nisan, N., RL ⊆ SC, Computational Complexity, 1994, 4 (1): 1–11, doi:10.1007/BF01205052, An earlier version of this paper appeared at the 1992 Symposium on Theory of Computing.
七月 04, 2023
複雜度, 在計算複雜度理論領域內, 有限錯誤機率對數空間, bounded, error, probabilistic, logarithmic, space, 或者叫做bplp, 有限錯誤機率對數空間多項式時間, bounded, error, probabilistic, logarithmic, space, polynomial, time, 是一個使用機率圖靈機可以在多項式時間時間以及對數空間解決的問題, 但是有雙邊錯誤, sided, error, 這個類別的名稱類似bpp, 一個很接近但是沒有對數空間. 在計算複雜度理論領域內 BPL 有限錯誤機率對數空間 Bounded error Probabilistic Logarithmic space 1 或者叫做BPLP 有限錯誤機率對數空間多項式時間 Bounded error Probabilistic Logarithmic space Polynomial time 2 是一個使用機率圖靈機可以在多項式時間時間以及對數空間解決的問題 但是有雙邊錯誤 two sided error 這個類別的名稱類似BPP 一個很接近但是沒有對數空間限制的類別 BPL裡面的機率圖靈機會在回答接收或者拒絕的時候 犯下機率小於1 3的錯誤 這個被稱呼為雙邊錯誤 這裡1 3的常數是一個抽象的概念 任何0 x lt 1 2都可以滿足這個定義 藉由重複整個演算法 我們可以限縮誤差機率小於2 p x 這裡的p x 為任意多項式 並且不使用多項式時間和對數空間以上的資源 雖然雙邊錯誤比起單邊錯誤 回答特定答案時絕不會出錯 只有在另一個答案時會 更加一般化 RL和它的補集co RL包含在BPL裡面 BPL也包含在PL 一個相類似的複雜度類 不過其錯誤率恰為1 2而非小於1 2 裡面 就像PP一樣 PL可能需要花費很多次的計算來降低錯誤的機率 因此比較不實用 Nisan 1994 使用了一個弱的去隨機化結果證明BPL包含在SC裡面 3 這裡的SC是一個複雜度類 包含可以使用決定型圖靈機在多項式時間和多項式對數 polylogarithmic 空間解決的問題 換句話說 這個結論證明了 給予多項式對數空間 一個決定型機器可以模擬對數空間的機率演算法 參考資料 编辑 Complexity Zoo BPL 2010 10 19 原始内容存档于2010 07 27 Borodin A Cook S A Dymond P W Ruzzo W L Tompa M Two applications of inductive counting for complementation problems SIAM Journal on Computing 1989 18 3 559 578 doi 10 1137 0218038 Nisan N RL SC Computational Complexity 1994 4 1 1 11 doi 10 1007 BF01205052 An earlier version of this paper appeared at the 1992 Symposium on Theory of Computing 取自 https zh wikipedia org w index php title BPL 複雜度 amp oldid 64119040, 维基百科,wiki,书籍,书籍,图书馆,