BPP(複雜度)

佇咧算複雜度理論內底，BPP是佇多項式時間內以機率圖靈機解出的問題的集合，並且對所有的輸入，輸出結果有錯誤的概率佇咧三分之一之內。BPP這簡寫代表講 "Bounded-error " ( 有限錯誤 )，"Probabilistic " ( 機率的 )，"Polynomial time " ( 多項式時間 )。

所以這就是一个問題佇BPP集合內底，則存在一个演算法，此演算法允准轉銀角仔做隨機的決定，而且佇咧多項式時間內底結束。對這个演算法的任何輸入，伊攏愛佇小於三分之一的錯誤概率之下予出正確判斷，無論這一个問題的答案是 " 正確 " 抑是講 " 錯誤 "。

佇遮定義內底的三分之一是任意予定的。伊會當佇零與二分之一 ( 無包含零與二分之一家己 ) 之間的任意常數而且 BPP 集合維持無變 ( 當然這个常數著愛佮輸入值為啥物無關 )。原因是因為，雖然這演算法有錯誤的機率，但是只要咱加進行幾擺演算法，彼多數的答案攏是錯誤的機率會呈現指數衰減 [一] . 因此證明阮會當足簡單的架構一个閣較準確的演算法，干焦單純多重複幾擺這个演算法然後對逐改的答案作多數決。

BPP是大細上大的幾个 _ 實際的 _ 問題類別之一，代表大多數BPP問題攏有效率的概率演算法，因此以上一千四百九十七位法會當用這馬的機器快速取得解答。因為這个原因，阮對佗一寡問題抑是問題種類佇BPP內底有實用方面的興趣。

定義

一个語言 _ L _ 佇咧BPP內底，若是唯一這个語言存在一个概率圖靈機 _ M _，另外

_ M _ 對任何輸入攏佇咧多項式時間了後停止
嘿任何字串 _ x _ 佇咧 _ L _ 之內，著 _ M _ 輸入 _ x _ 了後，_ M _ 輸出一的機率大於或者是等於三分之二
嘿任何字串 _ x _ 無佇咧 _ L _ 之內，著 _ M _ 輸入 _ x _ 了後，_ M _ 輸出一的機率較細抑是三分之一，BPP會當干焦決定性圖靈機定義。一个語言 _ L _ 是佇咧BPP內底若是唯一个多項式 _ p _ 佮一个決定性圖靈機 _ M _，滿足

_ M _ 對任何輸入均操作多項式時間之內
嘿任何字串 _ x _ 佇咧 _ L _ 之內，嘿長度為 _ p _ ( | _ x _ | ) 的任意字串 _ y _，滿足 _ M ( x , y ) _=一這條件的機率超過抑是等於三分之二
嘿任何字串 _ x _ 無佇咧 _ L _ 之內，嘿長度為 _ p _ ( | _ x _ | ) 的任意字串 _ y _，滿足 _ M ( x , y ) _=一這條件的機率細於或者是等於三分之一

佮其他複雜度類別的關係

已知BPP佇咧取補集之下有封閉性；嘛會使講，BPP=Co-BPP。BPP敢是NP的子集猶原是一个公開的問題。另外咧NP敢是BPP彼个子集也是一个公開的問題；若是，著NP=RP並且PH$ \ subseteq $BPP( [二] ) ( 大多數人認為袂，因為這代表講對一寡足困難的NP-完全問題有實際的解法 )。這馬已知矣RP是BPP的子集，並且BPP是PP的子集。猶無清楚這兩个敢是嚴格仔集。BPP包括佇PH內底。因此之故，P=NP代表BPP=P，因為乎PH佇這个時陣會變成P。存在特定有夠強的偽亂數產生器是這領域內底大多數專家的猜想。這个猜想代表隨機性並無予多項式計算閣較濟能力：嘛會使講，P=RP=BPP。注意一般的產生器並無夠表示出結果；使用典型的亂數產生器實做的任何概率演算法，佮亂數的種子無關係，對某一寡特定的輸入會一直共出錯誤的答案 ( 就算講這一寡輸入可能蓋稀罕 )。咱嘛可得會著P=BPP，若指數時間等級等仝款E=$ { \ textrm { DTIME } } \ left ( 二 ^ { O ( n ) } \ right ) $ ( Babai et al . ) , 抑是講若E有指數的電路複雜性 ( Impagliazzo and Wigderson )。閣BPP包括佇i . o .-SUBEXP=$ \ bigcap _ { \ varepsilon > 零 } { \ hbox { i . o .-DTIME } } ( 二 ^ { n ^ { \ varepsilon } } ) $ 內底，若是EXPTIME並無等於MA( Babai et al . ) .

一个 Monte Carlo 演算法是一个 " 差不多正確 " 的隨機演算法。佮伊足成的拉斯維加斯演算法較，後者是一个永遠正確的隨機演算法，毋過隨機性佇咧有可能會回傳推算失敗。多項式時間之內的拉斯維加斯演算法會使用來定義ZPP這个複雜度類。

BPP包括佇P / poly內底，根據 Adleman 的理論，BPP是包括講P ( 複雜度 )內底的。; 的呢有影，根據這个事實證明的結果，彼每一个 BPP 的演算法，若輸入是有限長度的話，咱會當透過一个決定性演算法去揣有夠長的隨機字串來消除 BPP 的隨機特性。毋過問題因為揣著這个字串可能是足開時間的代誌。

其他的特性

有一段足長的時間，一个非常有名的題目已經知是BPP但無確定講敢是P，是質數檢測，也就是講求一个予定的數字敢若質數。毋過，佇二空空二年的論文 _ 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 ( 一千九百九十三 ) . " BPP has subexponential time simulations unless EXPTIME has publishable proofs " . _ Computational Complexity _ , 三 : 三百空七–三百十八 .
Russell Impagliazzo and Avi Wigderson ( 一千九百九十七 ) . " P=BPP if E requires exponential circuits : Derandomizing the XOR Lemma " . _ Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing _ , pp . 兩百二十–兩百二十九 . doi : 十 . 二十五分八千五百三十三分之一千一百四十五 . 二十五孵八千五百九十
Valentine Kabanets ( 兩千空三 ) . " CMPT 七百一十–Complexity Theory : Lecture 十六 " . Simon Fraser University .
Christos Papadimitriou . Computational Complexity 一 st edition . Addison Wesley . 一千九百九十三 . ISBN 空九二百空一四五五三千空八十二孵一 . 引文格式的一維護：趁著文本 ( link ) Pages 兩百五十七–兩百五十九 of section 十一孵三 : Random Sources . Pages 兩百六十九–兩百七十一 of section 十一孵四 : Circuit complexity .
Michael Sipser . Introduction to the Theory of Computation . PWS Publishing . 一千九百九十七 . ISBN 空白五百三十四鋪九九四千七百二十八-X . Section 十二 . 一 : The class BPP , pp . 三百三十六–三百三十九 .

外部連結

Princeton CS 五百九十七 E : Derandomization paper list
Harvard CS 兩百二十五 : Pseudorandomness