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集合維持不變(當然這個常數必須跟輸入值為何無關)。原因在於,雖然這演算法有錯誤的機率,但是只要我們多進行幾次演算法,那多數的答案都是錯誤的機率會呈現指數衰減 页面存档备份,存于. 因此證明我們可以很簡單的架構一個更準確的演算法,僅僅單純多重複幾次這個演算法然後對每次的答案作多數決。
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 BPP() (大多數人認為不會,因為這代表對一些很難的NP-完全 問題有著實際的解法)。現在已知RP是BPP的子集,並且BPP是PP的子集。 尚不清楚這兩個是否為嚴格子集。 BPP包含在PH裡面。因此之故,P=NP代表BPP=P,因為PH在這時會變成P。 存在特定夠強的偽亂數產生器 是這領域裡面大多數專家的猜想。這個猜想代表隨機性並不給予多項式計算更多的能力:換句話說,P=RP=BPP。注意一般的產生器並不足以表示出結果;使用典型的亂數產生器實做的任何概率演算法,與亂數的種子無關,對某一些特定的輸入會一直給出錯誤的答案(即使這一些輸入可能很稀少)。我們也可得到P = BPP ,若指數時間等級等同於E = (Babai et al.),或者若E有指數的電路複雜性 (Impagliazzo and Wigderson)。 又BPP包含在i.o.-SUBEXP = 裡面,若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. . : 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. 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. . PWS Publishing. 1997. ISBN 0-534-94728-X. Section 10.2.1: The class BPP, pp.336–339.