BPP_(複雜度)

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

要是一個問題在 **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 (複雜度)** 裡面的。; 的確，根據這個事實證明的結果，每一個 BPP 的演算法，只要輸入是有限長度的話，我們可以藉由一個決定性演算法去找足夠長的隨機字串來消除 BPP 的隨機特性。不過問題在於找到這個字串可能是很花費時間的事情。

## 其他特性

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

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

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

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

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

## 參考資料

* 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.  引文格式 1 維護：冗餘文本 (link) 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.

## 外部連結

* Princeton CS 597E: Derandomization paper list
* Harvard CS 225: Pseudorandomness