BPP (複雜度)

在計算複雜度理論裡面，BPP是在多項式時間內以機率圖靈機解出的問題的集合, 並且對所有的輸入，輸出結果有錯誤的概率在1/3之內。BPP這個簡寫代表"Bounded-error"(有限錯誤)，"Probabilistic"(機率的)，"Polynomial time"(多項式時間)。

BPP 演算法 (操作一次)
	產生的答案
正確解答	是	否
是	≥ 2/3	≤ 1/3
否	≤ 1/3	≥ 2/3
BPP 演算法 (操作k次)
	產生的答案
正確解答	是	否
是	> 1 − 2^−ck	< 2^−ck
否	< 2^−ck	> 1 − 2^−ck
對於某些常數 c > 0

要是一個問題在BPP集合裡面，則存在一個演算法，此演算法允許轉硬幣作隨機的決定，並在多項式時間內結束。對這個演算法的任何輸入，他都要在小於1/3的錯誤概率之下給出正確判斷，不論這一個問題的答案是"正確"或者"錯誤"。

在這裡定義裡面的1/3是任意給定的。它可以是在 0 與 1/2(不包含0與1/2自身) 之間的任意常數而BPP集合維持不變(當然這個常數必須跟輸入值為何無關)。原因在於，雖然這演算法有錯誤的機率，但是只要我們多進行幾次演算法，那多數的答案都是錯誤的機率會呈現指數衰減 [1]（頁面存檔備份，存於網際網路檔案館）. 因此證明我們可以很簡單的架構一個更準確的演算法，僅僅單純多重複幾次這個演算法然後對每次的答案作多數決。

BPP是大小最大的幾個實際的問題類別之一，代表大多數的BPP問題都有有效率的概率演算法，因此以上倏地方法可以用現在的機器快速取得解答。因為這個原因，我們對哪一些問題或問題種類在BPP裡面有著實用方面的興趣。

定義

一個語言L在BPP裡面，若且唯若這語言存在一個概率圖靈機 M，另

M對任何輸入均在多項式時間後停止
對任何字串x在L之內, 對M輸入x之後，M 輸出 1 的機率大於或者等於 2/3
對任何字串 x 不在 L之內, 對M輸入x之後，M 輸出 1 的機率小於或者等於 1/3

另外，BPP可以僅以決定性圖靈機定義。一個語言L是在BPP裡面若且唯若存在一個多項式p和一個決定性圖靈機M，滿足

M對任何輸入均操作多項式時間之內
對任何字串x在L之內, 對長度為 p(|x|)的任意字串y ，滿足 M(x,y) = 1 這條件的機率超過或等於2/3
對任何字串 x 不在 L之內, 對長度為 p(|x|)的任意字串 y ，滿足 M(x,y) = 1 這條件的機率小於或等於1/3

與其他複雜度類別的關係

已知 BPP 在取補集之下有封閉性; 換句話說, BPP=Co-BPP。 BPP是否是NP的子集仍舊是一個公開的問題。另外NP是否是BPP的子集也是個公開的問題; 如果是的話，則NP=RP並且PH $\subseteq$ BPP([2]) (大多數人認為不會，因為這代表對一些很難的NP-完全 問題有著實際的解法)。現在已知RP是BPP的子集，並且BPP是PP的子集。尚不清楚這兩個是否為嚴格子集。 BPP包含在PH裡面。因此之故，P=NP代表BPP=P，因為PH在這時會變成P。存在特定夠強的偽亂數產生器是這領域裡面大多數專家的猜想。這個猜想代表隨機性並不給予多項式計算更多的能力：換句話說，P=RP=BPP。注意一般的產生器並不足以表示出結果；使用典型的亂數產生器實做的任何概率演算法，與亂數的種子無關，對某一些特定的輸入會一直給出錯誤的答案(即使這一些輸入可能很稀少)。我們也可得到P = BPP ，若指數時間等級等同於E = ${\textrm {DTIME}}\left(2^{O(n)}\right)$ (Babai et al.),或者若E有指數的電路複雜性 (Impagliazzo and Wigderson)。又BPP包含在i.o.-SUBEXP = $\bigcap _{\varepsilon >0}{\hbox{i.o.-DTIME}}(2^{n^{\varepsilon }})$ 裡面，若EXPTIME並不等同於MA (Babai et al.).

一個Monte Carlo演算法是一個"差不多正確"的隨機演算法。與跟它很像的拉斯維加斯演算法比較，後者則是一個永遠正確的隨機演算法，不過隨機性在於有可能會回傳推算失敗。多項式時間之內的拉斯維加斯演算法可以用來定義ZPP這個複雜度類。

BPP包含在P/poly裡面，根據Adleman的理論，BPP是包含於P (複雜度)裡面的。^[1]; 的確，根據這個事實證明的結果，每一個BPP的演算法，只要輸入是有限長度的話，我們可以藉由一個決定性演算法去找足夠長的隨機字串來消除BPP的隨機特性。不過問題在於找到這個字串可能是很花費時間的事情。

其他特性

有很長一段時間, 一個非常有名的題目已知是BPP但不確定是否是P，是質數檢測，也就是求一個給定的數字是否是質數。然而,在2002年的論文 PRIMES is in P, Manindra Agrawal 與他的學生 Neeraj Kayal 和 Nitin Saxena為了這個問題找到了一決定性，多項式時間的演算法，因而證實這個問題是在P裡面。

一個很重要的範例問題已知在BPP內 (事實上在co-RP內)，但不知道是否在P之內。這問題是等同多項式檢定, 這問題在於決定一個多項式是否完全等同於一個零多項式。換句話說，是否存在任何變數數值的組合令這個多項式的結果不為零？這題目應均勻且隨意的從一個至少 d個值的有限集合取變數的值來達到有限機率的錯誤(d代表多項式的總次數)。^[2]

BPP是低對應於自己 , 代表一個能在常數時間內解決BPP問題的BPP機器 (一個BPP 啟示圖靈機) ，他的運算能力並不因此比沒有這能力的機器更強(或說，兩個不同機器定義出來的問題種類維持不變)。

BPP這個語言集合是以一個普通的圖靈機加上一個亂數的來源來定義。相對應的量子計算機語言集合則是BQP。

任何在BPP裡面的語言可以被多項式大小的布林線路來決定 (參見P/poly).^[3]

參考資料

^ Adleman, L. M. Two theorems on random polynomial time. Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing: 75–83. 1978.
^ Madhu Sudan and Shien Jin Ong. Massachusetts Institute of Technology: 6.841/18.405J Advanced Complexity Theory: Lecture 6: Randomized Algorithms, Properties of BPP. February 26, 2003. http://people.csail.mit.edu/madhu/ST03/scribe/lect06.pdf （頁面存檔備份，存於網際網路檔案館）
^ Leonard Adleman, Two theorems on random polynomial time, Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing, 1978, pp. 75–83.

László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson (1993). "BPP has subexponential time simulations unless EXPTIME has publishable proofs". Computational Complexity, 3:307–318.
Russell Impagliazzo and Avi Wigderson (1997). "P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma". Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 220–229. doi:10.1145/258533.258590
Valentine Kabanets (2003). "CMPT 710 – Complexity Theory: Lecture 16". Simon Fraser University.
Christos Papadimitriou. Computational Complexity 1st edition. Addison Wesley. 1993. ISBN 0-201-53082-1. Pages 257–259 of section 11.3: Random Sources. Pages 269–271 of section 11.4: Circuit complexity.
Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X. Section 10.2.1: The class BPP, pp.336–339.

外部連結

[1] Adleman, L. M. Two theorems on random polynomial time. Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing: 75–83. 1978.

[2] Madhu Sudan and Shien Jin Ong. Massachusetts Institute of Technology: 6.841/18.405J Advanced Complexity Theory: Lecture 6: Randomized Algorithms, Properties of BPP. February 26, 2003. http://people.csail.mit.edu/madhu/ST03/scribe/lect06.pdf （頁面存檔備份，存於網際網路檔案館）

[3] Leonard Adleman, Two theorems on random polynomial time, Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing, 1978, pp. 75–83.

[1]

[2]

[3]