BPP (計算複雑性理論)

BPPの概要

BPPとは、計算複雑性理論において重要な複雑性クラスの一つで、「Bounded-error Probabilistic Polynomial time」の略称です。このクラスは、確率的チューリング機械を用いたアルゴリズムによって、誤りの可能性が最大で1/3であり、かつ実行にかかる時間が多項式に依存する決定問題を扱います。

BPPの特性

BPPクラスに含まれる問題に対しては、コイントスを利用するなどのランダムな決定を行うことができる多項式時間のアルゴリズムが存在します。このアルゴリズムの特性として、解が「YES」である場合と「NO」である場合の両方において、最大1/3の確率で誤った結果を返す可能性があります。この「1/3」という誤り率は重要であり、実際には0以上1/2未満の任意の定数で置き換えも可能ですが、その定数が変わってもBPPの性質は変化しません。特筆すべきは、アルゴリズムを複数回実行し、得られた結果の多数決をとることによって、この誤りの確率が指数的に減少する点です。これにより、より高精度な解を導くアルゴリズムを構築することが可能です。

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

BPPは特定の性質を持っており、補問題に対して閉じた性質があります。すなわち、BPPの問題が「YES」となる場合、その補問題もまたBPPに含まれるため、BPP = co-BPPが成り立ちます。また、BPPはNPクラスとの関係が不明瞭なクラスとしても知られています。数学的に証明されていることは、PがBPPの部分集合であり、BPPがPHと呼ばれる計算層にも含まれることです。

しかしながら、NPがBPPに含まれるのか、またはその逆の関係にあるのか、さらにはBPPとNPが同一であるのかは、現在のところ分かっていません。これに加えて、誤り率が1/2以下の他のクラスPPは、NPを含むことが証明されています。

BPPの拡張

計算モデルとして、確率的チューリングマシンを拡張することで、量子計算に相当する新たなクラスBQPが登場します。BQP（量子多項式時間）は、BPPのアルゴリズムを量子的な方法で実現したものであり、量子コンピュータを用いた計算の複雑性を考える上で重要です。

関連するクラス

BPPに関連するクラスには、クラスPPとクラスRPが存在します。クラスPPはBPPと非常に似ていますが、その誤り率は高々1/2に制限されています。明らかにBPPはPPに含まれます。また、クラスRPは、解が「YES」の場合に限り最大1/2の誤り確率を持ち、解が「NO」の場合は絶対に誤りません。

まとめ

BPPは、確率的なアルゴリズムが決定問題を効率的に解決できることを示す重要なクラスです。特に、その誤り確率が制限されており、複数回の実行によって精度を高める手法は、計算理論やアルゴリズム研究の分野で広く応用されています。今後もBPPとその関連クラスに関する研究は、計算複雑性理論の進展に寄与することでしょう。

もう一度検索