檢視 BPP(複雜度) 的原始碼

佇咧算複雜度理論內底，'''BPP'''是佇多項式時間內以機率圖靈機解出的問題的集合，並且對所有的輸入，輸出結果有錯誤的概率佇咧三分之一之內。'''BPP'''這簡寫代表講 "'''B'''ounded-error " ( 有限錯誤 )，"'''P'''robabilistic " ( 機率的 )，"'''P'''olynomial 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

[[分類: 待校正]]