Loading article…
計算複雑性理論（コンピュータ科学の一分野）において、誤差が限定された確率的多項式時間（BPP ）とは、確率的チューリングマシンによって多項式時間で解ける決定問題のクラスであり、すべてのインスタンスにおいて誤差確率が1/3以下に制限される。BPP は実用的な問題クラスの中で最も大きなものの1つであり、 BPPで関心のある問題のほとんどには、実際の最新のマシンで高速に実行できる 効率的な確率的アルゴリズムが存在する。また、決定論的アルゴリズムは確率的アルゴリズムの特殊なケースであるため、 BPPには決定論的マシンで多項式時間で解ける問題のクラスであるPも含まれる。
非公式には、問題がBPPに属するとは、以下の特性を持つアルゴリズムが存在する場合をいう。
言語LがBPPに属するのは、確率的チューリング マシンMが存在し、
複雑性クラスZPPとは異なり、機械Mは、ランダムなコイン投げの結果に関係なく、すべての入力に対して多項式時間で実行する必要がある。
あるいは、BPPは決定性チューリングマシンのみを使用して定義することもできます。言語LがBPPに含まれるのは、多項式pと決定性チューリングマシンMが存在し、以下の条件を満たす場合に限ります。
この定義では、文字列y は確率的チューリングマシンが行うであろうランダムなコイン投げの出力に対応します。この定義は確率的チューリングマシンに言及していないため、一部の用途では好ましい場合があります。
実際には、エラー確率が 1/3 では許容できないかもしれませんが、定義における 1/3 の選択は任意です。定義を変更して1/3 の代わりに 0 から 1/2 (排他的) の間の任意の定数を使用しても、結果として得られる集合BPP は変わりません。たとえば、アルゴリズムが最大で 1/2 100の確率で間違っている可能性があるという制約でクラスを定義した場合、同じクラスの問題が得られます。エラー確率は定数である必要さえありません。一方では1/2 − n − cまでエラーを許容し、他方では2 − n cまでエラーを小さく要求することで、同じクラスの問題が定義されます。ここで、 cは任意の正の定数、nは入力の長さです。エラー確率の選択におけるこの柔軟性は、エラーが発生しやすいアルゴリズムを何度も実行し、実行結果の多数決を使用してより正確なアルゴリズムを得るという考えに基づいています。実行の多数決が間違っている可能性は、Chernoff 限界の結果として指数関数的に減少します。[ 1 ]
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 の定理によれば、その結果、P = NP の場合、 PH はPに縮退するため、P = BPPとなります。したがって、P = BPPまたはP ≠ NPまたは両方が成り立ちます。
アドルマンの定理によれば、 BPPの任意の言語への所属は多項式サイズのブール回路の族によって決定できるため、BPP はP/polyに含まれることになります。[ 5 ]実際、この事実の証明の結果として、制限された長さの入力に対して動作するすべてのBPPアルゴリズムは、固定されたランダム ビット列を使用して決定論的アルゴリズムにデランダム化できます。ただし、この列を見つけるにはコストがかかる場合があります。モンテ カルロ時間クラスに関するいくつかの弱い分離結果は、 Karpinski & Verbeek (1987a)によって証明されています。Karpinski & Verbeek ( 1987b)も参照してください。
クラス BPP は、補集合、和集合、積集合、連結に関して閉じている。
オラクルに関して言えば、PA = BPP AかつP B ≠ BPP BとなるようなオラクルAと B が存在することがわかっています。さらに、確率 1 の ランダム オラクルに関して言えば、 P = BPPであり、BPP はNPおよびco-NPに厳密に含まれています。[ 6 ]
神託の中には、（したがって） ) ) [ 7 ]は、次のように反復的に構築できます。固定されたE NP (相対化) 完全問題の場合、オラクルは、問題インスタンスの後に長さknのランダムな文字列( nはインスタンスの長さ、 kは適切な小さな定数) を付けてクエリを実行すると、高い確率で正しい回答を返します。n = 1 から始めます。長さnの問題の各インスタンスについて、オラクルの回答を固定します (以下の補題を参照)。インスタンスの出力を固定します。次に、インスタンスの後にkn の長さの文字列が続くクエリのインスタンス出力を提供し、次に、長さ ≤ ( k +1) nのクエリの出力を固定として扱い、長さn +1 のインスタンスに進みます。
補題—相対化されたE NPの問題 (具体的には、オラクルマシンコードと時間制約) が与えられた場合、部分的に構築されたオラクルと長さnの入力に対して、出力は 2 O ( n )個のオラクルの回答を指定することで固定できます。
マシンはシミュレートされ、オラクルの回答（既に固定されていないもの）はステップごとに固定されます。決定論的な計算ステップごとに、オラクルのクエリは最大で 1 つです。相対化された NP オラクルの場合、可能であれば計算パスを選択して基本オラクルの回答を固定することで出力を yes に固定します。そうでない場合は固定は不要で、いずれの場合も基本オラクルの回答はステップごとに最大 1 つです。2 O ( n )ステップあるため、補題が成り立ちます。
この補題は、（十分大きなkに対して）相対化されたE NP の解答に十分な文字列を残したまま構成を実行できることを保証します。また、相対化されたE NPについては、関数問題（関数オラクルと線形出力サイズが与えられた場合）であっても、指数関数的に小さい（線形指数を持つ）エラー確率であっても、線形時間で十分であることを保証できます。さらに、この構成は、任意のオラクル A が与えられた場合、オラクル B をP A ≤ P BおよびEXP NP A = EXP NP B = BPP Bとなるように配置できるという点で効果的です。また、ZPP =EXPオラクル（したがってZPP=BPP=EXP < NEXP）の場合、相対化された E 計算の解答を特別な非解答に固定することで、偽の解答が与えられないことを保証します。
特定の強力な擬似乱数生成器の存在は、この分野のほとんどの専門家によって推測されている。このような生成器は、多項式時間ランダム化アルゴリズムにおいて真の乱数を置き換えることができ、区別できない結果を生み出す。これらの生成器が存在するという推測は、ランダム性が多項式時間計算に追加の計算能力を与えないこと、つまりP = RP = BPPを意味する。より強く言えば、 P = BPPという仮定は、ある意味で強力な擬似乱数生成器の存在と同等である。[ 8 ]
László Babai、Lance Fortnow、Noam Nisan、およびAvi Wigdersonは、 EXPTIMEがMAに縮退しない限り、BPPは[ 9 ]に含まれることを示した。
無限に頻繁にSUBEXPを表すio-SUBEXPクラスには、無限に多くの入力サイズに対して準指数時間アルゴリズムを持つ問題が含まれています。また、多項式階層とEに関してE PHとして定義される指数時間階層がEに縮退する場合、 P = BPPとなることも示されました。ただし、指数時間階層は通常縮退しないと予想されていることに注意してください。
Russell ImpagliazzoとAvi Wigdersonは、 Eに問題がある場合、
回路の複雑さが 2 Ω( n )である場合、P = BPPとなります。[ 10 ]
