BPP_(complexity)
で計算複雑性理論、有界誤り確率的多項式時間（BPPは）のクラスである意思決定の問題によって解ける確率的チューリングマシンで多項式時間のエラーを持つ確率はすべてのインスタンスのために離れて1/3から有界。BPPは、問題の最大の実用的なクラスの1つです。つまり、BPPで関心のあるほとんどの問題には、実際の最新のマシンですばやく実行できる効率的な確率的アルゴリズムがBPPにはPも含まれています、決定性マシンは確率的マシンの特殊なケースであるため、決定性マシンを使用して多項式時間で解決可能な問題のクラス。
BPPアルゴリズム（1回実行） 答え 生産
正しい 答え
はい 番号
はい ≥2/ 3 ≤1/ 3
番号 ≤1/ 3 ≥2/ 3
BPPアルゴリズム（k回実行）
答え 生産
正しい 答え
はい 番号
はい > 1 − 2 − ck
<2 − ck
番号 <2 − ck
> 1 − 2 − ck
定数c > 0の場合
非公式には、次のプロパティを持つアルゴリズムがある場合、BPPに問題が
コインを投げてランダムな決定をすることができます
多項式時間で実行することが保証されています
アルゴリズムを実行すると、答えがYESかNOかに関係なく、最大で1/3の確率で間違った答えが返されます。
コンテンツ
1 意味
2 問題
3 関連クラス
4 複雑さ-理論的特性
4.1 閉鎖特性 4.2 相対化
5 ランダム化解除
6 も参照してください
7 参考文献
8 外部リンク
意味
言語Lは、確率的チューリングマシンMが存在する場合に限り、BPPに含まれます。
Mは、すべての入力で多項式時間実行されます
すべてのためのxにおけるL、M 1を出力する確率の大きいよりも、または2/3に等しいです
Lにないすべてのxについて、Mは1/3以下の確率で1を出力します。
複雑度クラスZPPとは異なり、マシンMは、ランダムなコイントスの結果に関係なく、すべての入力で多項式時間実行する必要が
または、決定論的チューリングマシンのみを使用してBPPを定義することもできます。言語Lは、多項式pと決定論的チューリングマシンMが存在する場合にのみ、BPPに含まれます。
Mは、すべての入力で多項式時間実行されます
L内のすべてのxについて、次の条件を満たす長さp（| x |）の文字列yの割合。 （（ 、 y ）。= 1
{M（x、y）= 1}
2/3以上
Lにないすべてのxについて、長さp（| x |）の文字列yの割合は、 （（ 、 y ）。= 1
{M（x、y）= 1}
1/3以下
この定義では、文字列yは、確率的チューリングマシンが作成したランダムコイントスの出力に対応します。一部のアプリケーションでは、確率的チューリングマシンについて言及していないため、この定義が推奨されます。
実際には、1/3のエラー確率は許容できない場合がありますが、定義での1/3の選択は任意です。1/3の代わりに0から1/2（排他的）までの定数を使用するように定義を変更しても、結果のセットBPPは変更されません。たとえば、アルゴリズムが最大で1/2 100の確率で間違っている可能性があるという制限付きでクラスを定義した場合、同じクラスの問題が発生します。誤り確率も一定である必要はない。問題の同じクラスは1/2のように高いとしてエラーを可能にすることによって定義される- N – 、C 1手で、又は小2のようにエラー必要- N Cの一方、ここで、cは任意の正の定数、nは入力の長さです。エラー確率の選択におけるこの柔軟性は、エラーが発生しやすいアルゴリズムを何度も実行し、実行の大部分の結果を使用してより正確なアルゴリズムを取得するという考えに基づいています。実行の大部分が間違っている可能性は、チェルノフの限界の結果として指数関数的に低下します。
問題
コンピュータサイエンスの未解決の問題： =
？{{ mathsf {P}} { overset {？} {=}} { mathsf {BPP}}}
（コンピュータサイエンスにおける未解決の問題）
Pのすべての問題は明らかにBPPにもただし、多くの問題がBPPにあることがわかっていますが、Pにあることはわかっそのような問題の数は減少しており、P = BPPであると推測されます。
長い間、BPPにあることが知られているが、Pにあることが知られていない最も有名な問題の1つは、与えられた数が素数であるかどうかを決定する問題でした。しかし、2002紙でPRIMESであるP、マニンドラ・アグラワルと彼の学生ニラジュ・カヤルとニティン・サクセナはのでそれがであることを示し、この問題に対する決定性多項式時間アルゴリズムを発見したP。
問題の重要な例BPP（で、実際に共同RP）はまだであることが知られていないPは、ある多項式同一性試験、あなたは値へのアクセスを持っている場合、多項式は、ゼロ多項式と同一に等しいかどうかを決定する問題任意の入力の多項式の、ただし係数には適用されません。言い換えると、ゼロ以外の多項式がこれらの値で評価されたときに結果がゼロ以外になるように、変数に値が割り当てられていますか？有界誤差確率を達成するには、少なくともd個の値の有限サブセットから各変数の値をランダムに均一に選択するだけで十分です。ここで、dは多項式の次数の合計です。
関連クラス
ランダム性へのアクセスがBPPの定義から削除されると、複雑度クラスPが得られます。クラスの定義では、通常のチューリングマシンを量子コンピューターに置き換えると、クラスBQPが得られます。
BPPに事後選択を追加するか、計算パスの長さを変えると、クラスBPPパスが得られます。 BPPパスにはNPが含まれていることが知られており、対応する量子のPostBQPに含まれています。
Aモンテカルロアルゴリズムは、ある無作為化アルゴリズムが正しいことがありそうです。クラスBPPの問題には、実行時間が多項式で制限されたモンテカルロアルゴリズムがこれは、正解を出力するか、低い確率で「失敗」を出力するランダム化アルゴリズムであるラスベガスアルゴリズムと比較されます。クラスZPPを定義するために、実行時間が多項式に制限されたラスベガスアルゴリズムが使用されます。あるいは、ZPPには、常に正しく、多項式の実行時間が予想される確率的アルゴリズムが含まれています。これは、超多項式時間で実行される可能性があるため、多項式時間アルゴリズムであると言うよりも弱いですが、確率は非常に低くなります。
複雑さ-理論的特性
PSPACE内で
Pを一般化する他の確率的複雑度クラス（ZPP、 RP、co-RP、 BQP、 PP）
に関連するBPP
。これらの封じ込めのいずれかが厳格であるかどうかは不明です。
BPPは補集合の下で閉じられることが知られています; つまり、BPP = co-BPPです。BPP自体は低いため、BPPの問題を即座に解決する能力を備えたBPPマシン（BPPオラクルマシン）は、この余分な能力を備えていないマシンよりも強力ではありません。記号では、BPP BPP = BPP。
関係BPPとNPは不明である：かどうかは知られていないBPPがあるサブセットのNP、NPはのサブセットであるBPPまたはどちらも。場合NPが中に含まれているBPP、それはのための実用的なソリューションを暗示するからである可能性は低いと考えられ、NP完全問題は、NP = RPとPH ⊆ BPPを。
RPはBPPのサブセットであり、BPPはPPのサブセットであることが知られています。PがPSPACEの厳密なサブセットであるかどうかさえわからないため、これら2つが厳密なサブセットであるかどうかは不明です。BPPは、多項式階層の2番目のレベルに含まれているため、PHに含まれています。より正確には、シプサ-ロートマンの定理は次のように述べています。 NS⊆
Σ2 Π 2
{{ mathsf {BPP}} subseteq Sigma _ {2} cap Pi _ {2}}
。その結果、この場合、PHはPに崩壊するため、P = NPはP = BPPになります。したがって、P = BPPまたはP ≠ NP、あるいはその両方です。
Adlemanの定理は、BPPの任意の言語のメンバーシップは、多項式サイズのブール回路のファミリーによって決定できると述べています。つまり、BPPはP / polyに含まれています。実際、この事実の証明の結果として、制限された長さの入力で動作するすべてのBPPアルゴリズムは、ランダムビットの固定文字列を使用して決定論的アルゴリズムに非ランダム化できます。ただし、この文字列を見つけるのはコストがかかる場合がモンテカルロ時間クラスのためのいくつかの弱い分離結果がで証明されたKarpinski＆ファーベーク（1987A）も参照Karpinski＆ファーベーク（1987b）を。
閉鎖特性
クラスBPPは、補完、和集合、および共通部分の下で閉じられます。
相対化 ランダム化解除 も参照してくださいRP ZPP BQP 参考文献 外部リンク
神託に対して、我々は、その神託AおよびBが存在することを知っているP A = BPP AおよびP B ≠ BPP Bは。さらに、確率1のランダムオラクルと比較して、P = BPPおよびBPPは、NPおよびco-NPに厳密に含まれています。
BPP = EXP NP（したがって、P
補題は、（十分に大きいkの場合）、相対化されたENP回答に十分な文字列を残したまま構築を実行できることを保証します。また、相対化されたE NPの場合、関数の問題（関数オラクルと線形出力サイズが指定されている場合）および指数関数的に小さい（線形指数の）エラー確率でも、線形時間が十分であることを確認できます。また、この構成では、我々はP有することのOracle Bを手配することができ、その与えられた任意のOracle Aに有効であるA ≤P B及びEXP NP A = EXP NP B = BPP Bを。また、ZPP = EXPオラクル（したがってZPP = BPP = EXP
特定強いの存在擬似乱数がされて推測フィールドのほとんどの専門家によって。この予想は、ランダム性が多項式時間計算に追加の計算能力を与えないことを意味します。つまり、P = RP = BPPです。通常のジェネレーターでは、この結果を表示するのに十分ではないことに注意して一般的な乱数ジェネレーターを使用して実装された確率的アルゴリズムは、シードに関係なく、特定の入力で常に誤った結果を生成します（ただし、これらの入力はまれな場合があります）。
ラスズロ・ババイ、ランス・フォートナウ、ノアン・ニッサン、およびアビ・ウィグダーソンがない限りことを示しEXPTIMEはに崩壊MA、BPPの中に含まれているio-SUBEXP = ⋂ ε >>0 io-DTIME（（ 2 ε）。 {{ textsf {io-SUBEXP}} = bigcap nolimits _ { varepsilon> 0} { textsf {io-DTIME}} left（2 ^ {n ^ { varepsilon}} right）。 }
0}{textsf {i.o.-DTIME}}left(2^{n^{varepsilon }}right).}””> 無限に頻繁にSUBEXPを表すクラスio-SUBEXPには、無限に多くの入力サイズに対して指数関数以下の時間アルゴリズムを持つ問題が含まれています。彼らはまた、示されたP = BPPがに関して定義される指数時間階層、場合多項式階層及びEとしてE PHは、に崩壊E。ただし、指数時間階層は通常、崩壊しないと推測されることに注意して
ラッセル・インパリアッツォとアヴィ・ヴィグダーソンは、Eに問題があれば、どこで E = I E（（ 2 O （（ ）。
）。 {{ mathsf {E}} = { mathsf {DTIME}} left（2 ^ {O（n）} right）、}
回路計算量は2Ω（n）で、P = BPPです。
複雑さのクラスのリスト
^ Valentine Kabanets、 CMPT 710-複雑性理論：講義16、2003年10月28日 ^ マデュ・スーダンとシエン・ジン・オン。マサチューセッツ工科大学：6.841 / 18.405J高度な複雑性理論：講義6：ランダム化アルゴリズム、BPPのプロパティ。
^ BPPpath アーカイブで2013年6月3日ウェイバックマシンで複雑動物園 のアーカイブで2019年8月27日ウェイバックマシン ^ ランス・フォートノフとビル・ガサルチ、量子性を引き出す、2005年12月20日 ^ Adleman、LM（1978）。「ランダム多項式時間に関する2つの定理」。コンピューティングの基礎に関する第19回IEEEシンポジウムの議事録。pp。75–83。
^ ベネット、チャールズH。; Gill、John（1981）、「Relative to a Random Oracle A、P ^ A！= NP ^ A！= co-NP ^ A with Probability 1」、SIAM Journal on Computing、10（1）：96–113、doi：10.1137 / 0210008、ISSN 1095-7111 ^ Heller、Hans（1986）、「相対化された指数関数的および確率的複雑性クラスについて」、Information and Control、71（3）：231–243、doi：10.1016 / S0019-9958（86）80012-2
^ ババイ、ラースロー; フォートノフ、ランス; ニサン、ノアム; ウィグダーソン、アヴィ（1993）。「EXPTIMEに公開可能な証明がない限り、BPPには指数以下の時間シミュレーションがあります」。計算の複雑さ。3：307–318。土井：10.1007 / bf01275486。
^ ラッセルインパリアッツォとアヴィウィグダーソン（1997）。「Eが指数回路を必要とする場合のP = BPP：XOR補題の非ランダム化」。コンピューティング理論に関する第29回ACMシンポジウムの議事録、 pp。220–229。土井： 10.1145 / 258533.258590
バレンタインカバネッツ（2003）。「CMPT710–複雑性理論：講義16」。サイモンフレイザー大学。
クリストス・パパディミトリオウ（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、pp。336–339。
Karpinski、Marek ; Verbeek、Rutger（1987a）。「ランダム性、証明可能性、モンテカルロ時間と空間の分離」。コンピュータサイエンスの講義ノート。270：189–207。
Karpinski、Marek ; Verbeek、Rutger（1987b）。「モンテカルロ空間の構成可能関数と確率的複雑度クラスの分離結果について」。情報と計算。75（2）：178–189。土井：10.1016 / 0890-5401（87）90057-5。
アローラ、サンジーブ; ボアズバラク（2009）。「計算の複雑さ：現代的なアプローチ」。
Princeton CS 597E：ランダム化解除ペーパーリスト
ハーバード CS225 ：ウェイバックマシンで2003年8月5日にアーカイブされた疑似ランダム性”