BPP（複雑性）

計算複雑性理論（コンピュータ科学の一分野）において、誤差が限定された確率的多項式時間（BPP ）とは、確率的チューリングマシンによって多項式時間で解ける決定問題のクラスであり、すべてのインスタンスにおいて誤差確率が1/3以下に制限される。BPP は実用的な問題クラスの中で最も大きなものの1つであり、 BPPで関心のある問題のほとんどには、実際の最新のマシンで高速に実行できる 効率的な確率的アルゴリズムが存在する。また、決定論的アルゴリズムは確率的アルゴリズムの特殊なケースであるため、 BPPには決定論的マシンで多項式時間で解ける問題のクラスであるPも含まれる。

非公式には、問題がBPPに属するとは、以下の特性を持つアルゴリズムが存在する場合をいう。

• コインを投げてランダムな決定を下すことは許可されています
• 多項式時間で実行されることが保証されています
• アルゴリズムを一度実行すると、答えがYESかNOかにかかわらず、間違った答えを出す確率は最大で1/3です。

言語LがBPPに属するのは、確率的チューリング マシンMが存在し、

• Mはすべての入力に対して多項式時間で実行される。
• Lのすべてのxに対して、M は2/3 以上の確率で 1 を出力する。
• Lに含まれないすべてのxについて、Mは1/3以下の確率で1を出力する。

複雑性クラスZPPとは異なり、機械Mは、ランダムなコイン投げの結果に関係なく、すべての入力に対して多項式時間で実行する必要がある。

あるいは、BPPは決定性チューリングマシンのみを使用して定義することもできます。言語LがBPPに含まれるのは、多項式pと決定性チューリングマシンMが存在し、以下の条件を満たす場合に限ります。

• Mはすべての入力に対して多項式時間で実行される。
• Lのすべてのxに対して、長さp (| x |)の文字列yのうち、次の条件を満たすものの割合${\displaystyle M(x,y)=1}$2/3以上である
• Lに含まれないすべてのxに対して、長さp (| x |)の文字列yのうち、次の条件を満たすものの割合${\displaystyle M(x,y)=1}$1/3以下である

この定義では、文字列y は確率的チューリングマシンが行うであろうランダムなコイン投げの出力に対応します。この定義は確率的チューリングマシンに言及していないため、一部の用途では好ましい場合があります。

実際には、エラー確率が 1/3 では許容できないかもしれませんが、定義における 1/3 の選択は任意です。定義を変更して1/3 の代わりに 0 から 1/2 (排他的) の間の任意の定数を使用しても、結果として得られる集合BPP は変わりません。たとえば、アルゴリズムが最大で 1/2 ¹⁰⁰の確率で間違っている可能性があるという制約でクラスを定義した場合、同じクラスの問題が得られます。エラー確率は定数である必要さえありません。一方では1/2 − n ^{− c}までエラーを許容し、他方では2 ^{− n c}までエラーを小さく要求することで、同じクラスの問題が定義されます。ここで、 cは任意の正の定数、nは入力の長さです。エラー確率の選択におけるこの柔軟性は、エラーが発生しやすいアルゴリズムを何度も実行し、実行結果の多数決を使用してより正確なアルゴリズムを得るという考えに基づいています。実行の多数決が間違っている可能性は、Chernoff 限界の結果として指数関数的に減少します。^{[ 1 ]}

コンピュータサイエンスにおける未解決問題

⁠${\displaystyle {\mathsf {P}}{\overset {?}{=}}{\mathsf {BPP}}}$⁠

コンピュータサイエンスにおける未解決問題

Pに含まれる問題はすべてBPPにも含まれていることは明らかです。しかし、BPPに含まれることが知られているものの、 Pに含まれることが知られていない問題も数多く存在します。そのような問題の数は減少傾向にあり、P = BPPであると推測されています。

長い間、BPPに含まれることが知られているがPに含まれることが知られていない最も有名な問題の 1 つは、与えられた数が素数かどうかを判定する問題でした。しかし、2002 年の論文PRIMES is in Pで、Manindra Agrawalと彼の学生Neeraj KayalおよびNitin Saxena は、この問題に対する決定論的な多項式時間アルゴリズムを発見し、この問題がPに含まれることを示しました。

BPP（実際にはco-RP ）における重要な問題で、Pに含まれることがまだ知られていない例として、多項式の恒等性判定があります。これは、任意の入力に対して多項式の値はわかるが係数はわからない場合に、多項式がゼロ多項式と恒等的に等しいかどうかを判定する問題です。言い換えれば、これらの値に対して非ゼロ多項式を評価したときに結果が非ゼロになるような変数への値の割り当ては存在するのでしょうか？ 少なくともd個の値の有限部分集合から各変数の値を一様にランダムに選択すれば、誤差確率を制限できます。ここでdは多項式の総次数です。^{[ 2 ]}

BPPの定義からランダム性へのアクセスを取り除くと、複雑性クラスPが得られます。このクラスの定義において、通常のチューリングマシンを量子コンピュータに置き換えると、クラスBQPが得られます。

BPPに事後選択を追加したり、計算パスの長さが異なることを許容したりすると、クラスBPP_パスが得られます。^{[ 3 ]} BPP_パスはNPを含むことが知られており、その量子版であるPostBQPに含まれています。

モンテカルロアルゴリズムは、正解となる可能性が高いランダム化アルゴリズムです。BPPクラスの問題には、実行時間が多項式で制限されるモンテカルロアルゴリズムがあります。これに対し、ラスベガスアルゴリズムは、正解を出力するか、低い確率で「失敗」を出力するランダム化アルゴリズムです。実行時間が多項式で制限されるラスベガスアルゴリズムは、ZPPクラスを定義するために使用されます。あるいは、ZPPには、常に正解で、期待される実行時間が多項式である確率的アルゴリズムが含まれます。これは、実行時間が多項式時間を超える可能性はあるものの、その確率は非常に低いため、多項式時間アルゴリズムであると言うよりも弱い表現です。

BPPは補数に関して閉じていることが知られています。つまり、BPP = co-BPPです。BPPはそれ自体に対して低い値であり、 BPP問題を瞬時に解く能力を持つBPPマシン( BPPオラクル マシン) は、この追加能力を持たないマシンよりも強力ではありません。記号で表すと、BPP ^BPP = BPP となります。

BPPとNPの関係は不明です。BPPがNPの部分集合なのか、NPがBPPの部分集合なのか、あるいはどちらでもないのかは不明です。NPがBPPに含まれる場合（NP完全問題に対する実用的な解が存在することになるため、これは考えにくい） 、 NP = RPかつPH ⊆ BPPとなります。^{[ 4 ]}

RP はBPPの部分集合であり、BPPはPPの部分集合であることが知られています。PがPSPACEの厳密な部分集合であるかどうかもわからないため、これら 2 つが厳密な部分集合であるかどうかはわかりません。BPPは多項式階層の第 2 レベルに含まれているため、PHに含まれています。より正確には、Sipser–Lautemann の定理によれば、$\displaystyle {\mathsf {BPP}}\subseteq \Sigma _{2}\cap \Pi _{2}}$その結果、P = NP の場合、 PH はPに縮退するため、P = BPPとなります。したがって、P = BPPまたはP ≠ NPまたは両方が成り立ちます。

アドルマンの定理によれば、 BPPの任意の言語への所属は多項式サイズのブール回路の族によって決定できるため、BPP はP/polyに含まれることになります。^{[ 5 ]}実際、この事実の証明の結果として、制限された長さの入力に対して動作するすべてのBPPアルゴリズムは、固定されたランダム ビット列を使用して決定論的アルゴリズムにデランダム化できます。ただし、この列を見つけるにはコストがかかる場合があります。モンテ カルロ時間クラスに関するいくつかの弱い分離結果は、 Karpinski & Verbeek (1987a)によって証明されています。Karpinski & Verbeek ( 1987b)も参照してください。

特定の強力な擬似乱数生成器の存在は、この分野のほとんどの専門家によって推測されている。このような生成器は、多項式時間ランダム化アルゴリズムにおいて真の乱数を置き換えることができ、区別できない結果を生み出す。これらの生成器が存在するという推測は、ランダム性が多項式時間計算に追加の計算能力を与えないこと、つまりP = RP = BPPを意味する。より強く言えば、 P = BPPという仮定は、ある意味で強力な擬似乱数生成器の存在と同等である。^{[ 8 ]}

László Babai、Lance Fortnow、Noam Nisan、およびAvi Wigdersonは、 EXPTIMEがMAに縮退しない限り、BPPは^{[ 9 ]}に含まれることを示した。

${\displaystyle {\textsf {io-SUBEXP}}=\bigcap \nolimits _{\varepsilon >0}{\textsf {io-DTIME}}\left(2^{n^{\varepsilon }}\right).}$

無限に頻繁にSUBEXPを表すio-SUBEXPクラスには、無限に多くの入力サイズに対して準指数時間アルゴリズムを持つ問題が含まれています。また、多項式階層とEに関してE ^PHとして定義される指数時間階層がEに縮退する場合、 P = BPPとなることも示されました。ただし、指数時間階層は通常縮退しないと予想されていることに注意してください。

Russell ImpagliazzoとAvi Wigdersonは、 Eに問題がある場合、

${\displaystyle {\mathsf {E}}={\mathsf {DTIME}}\left(2^{O(n)}\right),}$

回路の複雑さが 2 ^{Ω( n )}である場合、P = BPPとなります。^{[ 10 ]}

• RP
• ZPP
• BQP
• 複雑性クラスのリスト

• Valentine Kabanets (2003). "CMPT 710 – 複雑性理論: 講義 16". Simon Fraser University .
• クリストス・パパディミトリウ（1993）。計算複雑性（第1 版）。アディソン・ウェスリー。ISBN 0-201-53082-1。第11.3節「ランダムソース」の257～259ページ。第11.4節「回路の複雑さ」の269～271ページ。
• マイケル・シプサー（1997）。計算理論入門。PWS出版。ISBN 0-534-94728-X。セクション 10.2.1: クラス BPP、 336～339 ページ。
• Karpinski, Marek ; Verbeek, Rutger (1987a). "ランダム性、証明可能性、モンテカルロ時間と空間の分離". Börger, Egon (編). Computation Theory and Logic, In Memory of Dieter Rödding . Lecture Notes in Computer Science. Vol.  270. Springer. pp. 189–207 . doi : 10.1007/3-540-18170-9_166 . 
• Karpinski, Marek ; Verbeek, Rutger (1987b). "モンテカルロ空間の構成可能関数と確率的複雑性クラスの分離結果について" .Information and Computation . 75 (2): 178–189 . doi : 10.1016/0890-5401(87)90057-5 .
• Arora, Sanjeev; Boaz Barak (2009). 「計算複雑性：現代的アプローチ」

• プリンストン大学コンピュータサイエンス597E：脱ランダム化に関する論文リスト
• ハーバード大学CS 225：擬似乱数性（2003年8月5日にWayback Machineにアーカイブ済み）