Back

ⓘ BPP, 計算複雑性理論. 計算複雑性理論において、 BPP とは、確率的チューリングマシンによって、誤り確率が高々13で多項式時間で解ける決定問題の複雑性クラスである。Boun ..




                                     

ⓘ BPP (計算複雑性理論)

計算複雑性理論において、 BPP とは、確率的チューリングマシンによって、誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Probabilistic Polynomial timeの頭文字をとったものである。 ある問題が BPP に属するなら、コイントスなどによるランダムな決定を許す多項式時間で実行可能なアルゴリズムが存在する。そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。

定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、 BPP は変化しない。 これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。 この性質は複数回アルゴリズムを実行し、解の多数決をとることにより、高い精度のアルゴリズムを作る事を可能にする。

                                     

1. 他の計算量クラスとの関係

BPP は、補問題について閉じていることが知られている。つまり、 BPP =co- BPP である。 このクラスは特に NP との位置が不定のクラスである。 P ⊆ {\displaystyle \subseteq } BPP ⊆ {\displaystyle \subseteq } PH は証明されている。 しかし NP ⊆ {\displaystyle \subseteq } BPP なのか、 BPP ⊆ {\displaystyle \subseteq } NP なのか、あるいは BPP = NP なのかは不明である。

なおこのクラスとよく似た誤り確率が高々1/2 のクラス(クラス PP )は NP を含むことが証明されている。

確率的チューリングマシンを少し拡張すると、量子チューリングマシンができるのと同じように、 BPP の量子コンピュータに対応する計算量のクラスとして BQP が存在する。

                                     

2. 関連するクラス

  • クラス RP - YES であるときの誤り確率は高々1/2 であり、NO のときは絶対に間違えないクラス。
  • クラス PP - クラス BPP とほとんど同じ概念のクラスだがこちらは誤り確率が高々1/2である。当然ながら BPP   ⊆ {\displaystyle \subseteq } PP である。
                                     
  • 計算複雑性理論 けいさんふくざつせいりろん computational complexity theory とは 計算 機科学における 計算 理論 の一分野であり アルゴリズムのスケーラビリティや 特定の 計算 問題の解法の 複雑性 計算 問題の困難さ などを数学的に扱う 計算 量 理論 計算 の 複雑 さの 理論 計算複雑 度の理論ともいう
  • BPP 計算複雑性理論 における 複雑 さのクラスの一つ BPP 計算複雑性理論 ブラックパンサー党 Black Panther Party 色深度で用いられる単位の一つ bits per pixel の略 BPP ホールディングス - イギリスの国立大学運営持株会社 国営 Basic Printing
  • 計算複雑性理論 において 複雑性 クラス E とは 決定 性 チューリング機械で 2O n の時間で解ける決定問題の集合である これはすなわち 複雑性 クラス DTIME 2O n に等しい E は類似のクラス EXPTIME よりも 理論 上の重要性が低いとされる それは 多項式時間多対一還元において閉じていないためである
  • 計算複雑性理論 におけるRP randomized polynomial time とは 以下の3つの属性を持つ確率的チューリング機械で解ける問題の 複雑性 クラスである 入力長に対して常に多項式時間かかる 正解が NO である場合 常に NO を返す 正解が YES である場合 確率 ½ 以上で YES
  • 計算複雑性理論 において 複雑性 クラス PP とは 確率的チューリング機械で多項式時間で解ける決定問題の集合であり その際に間違う確率は常に 1 2 未満である PP は probabilistic polynomial time を意味する 1977年 Gill が定義した PP
  • 複雑性 クラス ふくざつせいクラス 英: Complexity class は 計算複雑性理論 において関連する 複雑性 の問題の集合を指す 典型的な 複雑性 クラスは以下のように定義される 抽象機械 M によりO f n の 計算 資源 R を使って解く事が出来る問題の集合 nは入力長
  • 計算複雑性理論 において BQPとは 量子コンピュータによって誤り確率が高々1 3で多項式時間で解ける決定問題の 複雑性 クラスである Bounded - error Quantum Polynomial time の頭文字をとったものである ある問題がBQPに属すなら 高い確率で正答を返し 多項式時間で実行
  • 計算 量 理論 におけるPとは多項式時間 polynomial time で解ける判定問題の集合である 判定問題のうち ある決定 性 チューリング機械によって多項式時間で解かれるものの全体をPで表す Pはしばしば 効率的に解ける 問題のクラスとして扱われる しかしながら RPや BPP