About: BPP (計算複雑性理論)

計算複雑性理論においてBPPとは、確率的チューリングマシンによって、誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Probabilistic Polynomial timeの頭文字をとったものである。ある問題がBPPに属するなら、コイントスなどによるランダムな決定を許す多項式時間で実行可能なアルゴリズムが存在する。そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、BPPは変化しない。これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。この性質は複数回アルゴリズムを実行し、解の多数決をとることにより、高い精度のアルゴリズムを作る事を可能にする。