ZPP_(complexity)
複雑性理論、ZPP（ゼロエラー確率的多項式時間）である複雑性クラスれる問題の確率チューリングマシンは、これらの特性を有するが存在します：
常に正しいYESまたはNOの答えを返します。
実行時間は、すべての入力を期待して多項式です。
PSPACE内で
Pを一般化する他の確率的複雑度クラス（RP、co-RP、 BPP、 BQP、 PP）
に関連するZPP
。これらの封じ込めのいずれかが厳格であるかどうかは不明です。
言い換えると、アルゴリズムが実行中に真にランダムなコインを反転することが許可されている場合、常に正しい答えが返され、サイズnの問題の場合、平均実行中のような多項式p（n）が時間はp（n）よりも短くなりますが、場合によってははるかに長くなることもこのようなアルゴリズムは、ラスベガスアルゴリズムと呼ばれます。
あるいは、ZPPは、次の特性を持つ確率的チューリングマシンが存在する問題のクラスとして定義できます。
常に多項式時間で実行されます。
「はい」、「いいえ」、または「わからない」という回答が返されます。
答えは常に「わからない」または「正解」のいずれかです。
すべての入力に対して最大で1/2の確率でDONOT KNOWを返します（それ以外の場合は正解）。
2つの定義は同等です。
ZPPの定義は確率的チューリングマシンに基づいていますが、明確にするために、それらに基づく他の複雑さのクラスにはBPPとRPが含まれることに注意してクラスBQPは、ランダム性を備えた別のマシンである量子コンピューターに基づいています。
コンテンツ
1 交差点の定義
2 証人と証拠
3 複雑さ-理論的特性
4 他のクラスへの接続
5 も参照してください
6 外部リンク
交差点の定義
クラスZPPは、クラスRPとco-RPの共通部分に正確に等しくなります。これは、多くの場合、ZPPの定義と見なされます。これを示すために、 RPとco-RPの両方にあるすべての問題には、次のようなラスベガスアルゴリズムがあることに最初に注意して
RPアルゴリズムAと（おそらく完全に異なる）co-RPアルゴリズムBの両方によって認識される言語Lがあるとします。
入力が与えられたら、入力に対してAを1ステップ実行します。YESが返された場合、答えはYESでなければなりません。それ以外の場合は、入力でBを1ステップ実行します。NOが返された場合、答えはNOでなければなりません。どちらも発生しない場合は、この手順を繰り返します。
間違った答えを出すことができるのは1台のマシンだけであり、そのマシンが各繰り返し中に間違った答えを出す可能性は最大で50％であることに注意してこれは、k番目のラウンドに到達する可能性がkで指数関数的に縮小することを意味し、予想される実行時間が多項式であることを示しています。これは、RP交差co-RPがZPPに含まれていることを示しています。
ことを示すためにZPPが中に含まれているRP交差する共同RP、我々は問題を解決するために、ラスベガスアルゴリズムCがあるとします。次に、次のRPアルゴリズムを構築できます。
Cを、予想される実行時間の少なくとも2倍の時間実行します。それが答えを与えるなら、その答えを与えなさい。停止する前に応答がない場合は、NOを指定します。
マルコフの不等式、我々はそれを停止する前に、それは答えが得られる可能性は少なくとも1/2です。これは、YESインスタンスで、停止してNOを生成することにより、間違った答えを出す可能性が最大で1/2であることを意味し、RPアルゴリズムの定義に適合します。CO-RPのアルゴリズムは、Cが「タイムアウトする」場合、それはYESを与えることを除いて、同じです。
証人と証拠
クラスNP、RP、およびZPPは、セットのメンバーシップの証明の観点から考えることができます。
定義： A検証：集合XのためのVは、そのようなことをチューリングマシンであります
場合Xはであり、X、文字列が存在するWようにVが（X、W）を受け付けると、
xがXにない場合、すべての文字列wについて、V（x、w）は拒否します。
文字列wは、メンバーシップの証明と考えることができます。効率的に検証できる短い証明（入力のサイズが多項式で囲まれた長さ）の場合（Vは多項式時間決定論的チューリングマシン）、文字列wはウィットネスと呼ばれます。
ノート：
定義は非常に非対称です。xがXにあることの証明は、単一の文字列です。xがXに含まれていないことの証明は、すべての文字列のコレクションであり、メンバーシップの証明ではありません。
証人の可用性は均一です。X内のすべてのxについて、証人が必要です。X内の特定のxを検証するのが難しすぎる場合はありませんが、ほとんどの場合はそうではありません。
証人は、伝統的に解釈された証拠である必要はありません。Vが確率的チューリングマシンであり、xがXにある場合、xを受け入れる可能性がある場合、その証拠は、運、直感、または天才によって、マシンをxを受け入れるように導くコイントスの文字列です。
共同概念は、非メンバーシップ、または補集合のメンバーシップの証明です。
クラスNP、RP、およびZPPは、メンバーシップの証人がいるセットです。クラスNPは、証人が存在することだけを要求します。それらは非常にまれかもしれません。2つのf（| x |）の可能な文字列のうち、fが多項式の場合、検証者が受け入れる必要があるのは1つだけです（xがXにある場合。xがXにない場合、文字列は検証者に受け入れられません）。
クラスRPおよびZPPの場合、ランダムに選択された文字列が目撃者になる可能性が
対応する共同クラスには、非会員の証人がいます。特に、co-RPは、xがXにない場合、ランダムに選択された文字列が非メンバーシップの目撃者になる可能性が高いセットのクラスです。ZPPは、ランダムな文字列がXのxの目撃者であるか、Xではないxの目撃者である可能性が高いセットのクラスです。
この定義をRP、co-RP、およびZPPの他の定義と接続するのは簡単です。確率的多項式時間チューリングマシンV * w（x）は、決定論的多項式時間チューリングマシンV（x、w）に対応し、V *のランダムテープを、次のシーケンスが書き込まれるVの2番目の入力テープに置き換えます。コイントス。ランダムな文字列として証人を選択することにより、検証者は、その確率Xがであるとき、Xを受け入れる確率的多項式時間チューリングマシンであるX大きい（1/2よりも大きい、と言う）であるが、ゼロであれば、X ∉ X（用RP）; XがXでない場合、Xを拒否することは大きいがゼロの場合のx ∈ X（のためのコ- RP）; Xのメンバーとしてxを正しく受け入れたり拒否したりすることは大きいですが、xを誤って受け入れたり拒否したりすることはありません（ZPPの場合）。
可能な証人のランダムな選択を繰り返すことにより、ランダムな文字列が証人である可能性が高いため、入力を受け入れるか拒否するための予想される多項式時間アルゴリズムが得られます。逆に、チューリングマシンが（任意のxに対して）多項式時間であると予想される場合、実行のかなりの部分が多項式時間で制限されている必要があり、そのような実行で使用されるコインシーケンスが証人になります。
ZPPはBPPと対比する必要がクラスBPPは、証人で十分ですが、証人を必要としません（したがって、BPPにはRP、co-RP、およびZPPが含まれます）。A BPPの言語は、XがXであり、Xがでない場合は逆にWの文字列の（クリア）過半数に拒否した場合、V（X、W）がwの文字列の（クリア）大部分に受け入れ有するX。単一の文字列wが決定的なものである必要はないため、一般に証明または証人と見なすことはできません。
複雑さ-理論的特性
ZPPは補完の下で閉じられることが知られています。つまり、ZPP = co-ZPPです。
ZPP自体は低いため、ZPPの問題を即座に解決する能力を備えたZPPマシン（ZPPオラクルマシン）は、この余分な能力を備えていないマシンよりも強力ではありません。記号では、ZPP ZPP = ZPPです。
ZPP NP BPP = ZPP NP。
NP BPPは、中に含まれているZPP NP。
他のクラスへの接続
以来ZPP = RP ∩ CORP、ZPPは明らかに、両方に含まれているRPとCORP。
クラスPはZPPに含まれており、一部のコンピューターサイエンティストは、P = ZPPであると推測しています。つまり、すべてのラスベガスアルゴリズムには決定論的な多項式時間の等価物が
ZPP = EXPTIMEに関連するオラクルが存在します。証明ZPP = EXPTIMEは、その意味するものであろうP ≠ ZPPとして、P ≠ EXPTIMEを（参照時間階層定理）。
も参照してください BPP RP
外部リンク
複雑さの動物園： ZPPクラスZPP