有界誤差 確率的 多項時間 (有界誤差 確率的 多項時間), BPP ( B ounded-error, P robabilistic, P olynomial time)는 計算 複雜度 理論 에서 確率的 튜링 機械 로 모든 問題에 對해서 最大 1/3의 誤謬가 發生하면서 多項時間 에 풀 수 있는 判定 問題 의 集合이다.

어떤 問題가 BPP 에 屬하면, 內部的으로 銅錢을 던져서 無作爲로 進行方向을 決定하여 이 問題를 풀 수 있는 알고리즘이 存在하고 이 알고리즘은 多項時間안에 實行된다. 이 알고리즘을 實行할 때, 잘못된 實行結果를 내놓을 確率은 最大 1/3이다. 여기서 잘못된 實行結果는 '예'나 '아니오'라는 對答을 내놓는 모든 境遇에 該當한다.

여기서 1/3이라는 確率이 특수한 意味를 가지는 것은 아니다. 1/3 代身 入力값에 따라 달라지지 않는 0과 1/2 사이의 適當한 確率을 指定해서 定義해도 BPP 의 集合은 變하지 않는다.

다른 複雜度 種類와 聯關性 [ 編輯 ]

BPP 는 餘集合 演算에 對해서 닫혀있다. 卽, BPP = co-BPP 이다. BPP 가 NP 의 部分集合 認知 與否는 아직까지 알려지지 않았다. NP 가 BPP 의 部分集合인지도 아직 알려지지 않았다. 萬若 NP 가 BPP 의 部分集合이면 NP = RP 이고 PH ⊆ BPP 이다. [1] (實際로 이것이 成立할 境遇에는 NP-完全 問題에 對한 效率的인 해가 存在하므로, 많은 이들은 이것이 成立하지는 않을 것으로 推定한다.). RP 와 co-RP 는 BPP 의 部分集合이고, BPP 는 PP 의 部分集合이라는 것이 알려졌으나 이 關係가 眞部分集合인지는 알려진 바가 없다. BPP 는 PH 의 部分集合이다.

性質 [ 編輯 ]

주어진 數字가 少數 인지 아닌지 判明하는 것은 오랫동안 BPP 에 屬하지만 P 에는 屬하지 않는 問題라고 많은 사람들이 생각해왔다. 그러나 最近에는 少數 判別度 P 라는 것이 밝혀졌다. 2002年 에 마닌드라 아그라왈과 그의 學生 니라즈 카얄, 니틴 삭세나 等이 決定論的으로 少數인지 判別하는 알고리즘을 開發한 것이다.

BPP 는 自己 自身에 비해 낮다 . 卽, BPP 問題를 卽時 解決할 수 있는 BPP 機械 ( BPP 信託機械 )는 이런 別途의 能力이 없는 機械보다 强力하지 않기 때문이다.

BPP는 亂數를 使用하는 一般的인 튜링 機械 에 該當한다. BQP 는 BPP와 비슷하지만 튜링 機械가 아닌 量子컴퓨터 에 該當한다.

어떤 言語가 BPP 에 屬하는지는 多項式 크기를 가진 불 回로 로 判定할 수 있다. 仔細한 內容은 回로 複雜度 를 參考하라.

外部 링크 [ 編輯 ]

• (英語) Princeton CS 597E: Derandomization paper list
• (英語) 類似亂數에 關한 하버드 講義資料 - 로그인 必要