BPP (複雜度)
維基百科,自由的 encyclopedia
在計算複雜度理論裏面,BPP是在多項式時間內以概率圖靈機解出的問題的集合, 並且對所有的輸入,輸出結果有錯誤的概率在1/3之內。BPP這個簡寫代表"Bounded-error"(有限錯誤),"Probabilistic"(概率的),"Polynomial time"(多項式時間)。
More information BPP 演算法 (操作一次), BPP 演算法 (操作k次) ...
BPP 演算法 (操作一次) | ||
---|---|---|
產生的答案 | ||
正確 解答 |
是 | 否 |
是 | ≥ 2/3 | ≤ 1/3 |
否 | ≤ 1/3 | ≥ 2/3 |
BPP 演算法 (操作k次) | ||
產生的答案 | ||
正確 解答 |
是 | 否 |
是 | > 1 − 2−ck | < 2−ck |
否 | < 2−ck | > 1 − 2−ck |
對於某些常數 c > 0 |
Close
要是一個問題在BPP集合裏面,則存在一個演算法,此演算法允許轉硬幣作隨機的決定,並在多項式時間內結束。 對這個演算法的任何輸入,他都要在小於1/3的錯誤概率之下給出正確判斷,不論這一個問題的答案是"正確"或者"錯誤"。
在這裏定義裏面的1/3是任意給定的。它可以是在 0 與 1/2(不包含0與1/2自身) 之間的 任意常數而BPP集合維持不變(當然這個常數必須跟輸入值為何無關)。原因在於,雖然這演算法有錯誤的概率,但是只要我們多進行幾次演算法,那多數的答案都是錯誤的概率會呈現指數衰減 [1](頁面存檔備份,存於互聯網檔案館). 因此證明我們可以很簡單的架構一個更準確的演算法,僅僅單純多重複幾次這個演算法然後對每次的答案作多數決。
BPP是大小最大的幾個實際的問題類別之一,代表大多數的BPP問題都有有效率的概率演算法,因此以上倏地方法可以用現在的機器快速取得解答。因為這個原因,我們對哪一些問題或問題種類在BPP裏面有着實用方面的興趣。