Loading article…
計算複雑性理論において、ZPP（ゼロエラー確率的多項式時間）とは、以下の特性を持つ確率的チューリングマシンが存在する問題の複雑性クラスのことである。
言い換えれば、アルゴリズムが実行中に真にランダムなコインを投げることが許される場合、常に正しい答えが返され、サイズnの問題に対して、平均実行時間が p(n) より短くなるような多項式 p(n ) が存在する。ただし、実行時間は時折、 p ( n ) より長くなる場合がある。このようなアルゴリズムは、ラスベガスアルゴリズムと呼ばれる。
あるいは、ZPPは、以下の特性を持つ確率的チューリングマシンが存在する問題のクラスとして定義することもできる。
この二つの定義は同義である。
ZPPの定義は確率的チューリングマシンに基づいているが、分かりやすくするために、これらに基づく他の複雑性クラスにはBPPとRPが含まれることに注意されたい。BQPクラスは、ランダム性を持つ別のマシン、すなわち量子コンピュータに基づいている。
クラスZPP は、クラスRPとco-RPの共通部分と完全に等しい。これは、しばしばZPPの定義とみなされる。これを示すために、まず、 RPとco-RP の両方に含まれるすべての問題には、次のようなラスベガスアルゴリズムが存在することに注目する。
常に1台のマシンだけが誤った答えを出す可能性があり、そのマシンが各繰り返しで誤った答えを出す確率は最大でも50%であることに注意してください。これは、k番目のラウンドに到達する確率がkに対して指数関数的に減少することを意味し、期待実行時間が多項式であることを示しています。これは、 RPとco-RPの交差がZPPに含まれることを示しています。
ZPPがRPとco-RPの交差に含まれることを示すために、問題を解くためのラスベガスアルゴリズムCがあると仮定します。すると、次のRPアルゴリズムを構築できます。
マルコフの不等式によれば、停止する前に答えが得られる確率は少なくとも 1/2 です。つまり、停止して NO を出すことで YES のインスタンスに対して誤った答えを出す確率は最大でも 1/2 であり、RPアルゴリズムの定義に合致しています。co -RPアルゴリズムは、C がタイムアウトした場合に YES を出す点を除いて、これと同一です。
クラスNP、RP、ZPPは、集合への所属の証明という観点から考えることができる。
定義：集合Xに対する検証器Vは、以下の条件を満たすチューリングマシンである。
文字列w はメンバーシップの証明と考えることができます。効率的に検証できる短い証明 (入力サイズの多項式で制限される長さ) ( Vは多項式時間決定性チューリングマシン)の場合、文字列wは証拠と呼ばれます。
注：
クラスNP、RP、ZPP は、メンバーシップの証拠となる要素を持つ集合です。クラスNP は、証拠となる要素が存在することのみを要求します。それらは非常にまれな場合もあります。f が多項式である場合、可能な文字列 2 f (| x |) のうち、検証者が受け入れる原因となる文字列は 1 つだけで十分です (x が X に含まれる場合。x が X に含まれない場合、検証者が受け入れる原因となる文字列はありません)。
クラスRPとZPPの場合、ランダムに選択された文字列は、おそらく証拠となるでしょう。
対応する共クラスには、非メンバーシップの証拠が存在する。具体的には、co-RPは、x が X に含まれない場合、任意のランダムに選択された文字列が非メンバーシップの証拠となる可能性が高い集合のクラスである。ZPPは、任意のランダムな文字列が、x が X に含まれるか、または x が X に含まれないかのどちらの場合でも、その証拠となる可能性が高い集合のクラスである。
この定義をRP、co-RP、ZPPの他の定義と関連付けるのは簡単です。確率的多項式時間チューリングマシンV* w ( x ) は、V*のランダム テープを、コイン フリップのシーケンスが書き込まれた V の 2 番目の入力テープに置き換えることにより、決定論的多項式時間チューリングマシンV ( x , w )に対応します。証人をランダム ストリングとして選択することにより、検証者は、x がXに含まれる場合に x を受け入れる確率は大きい (たとえば 1/2 より大きい) が、x ∉ Xの場合はゼロ( RPの場合)、x が X に含まれない場合に x を拒否する確率は大きいが、 x ∈ Xの場合はゼロ( co-RPの場合)、x をXのメンバーとして正しく受け入れるか拒否する確率は大きいが、 x を誤って受け入れるか拒否する確率はゼロ ( ZPPの場合) である確率的多項式時間チューリングマシンになります。
可能な証拠を繰り返しランダムに選択することで、ランダムな文字列が証拠となる確率が高くなり、入力の受理または拒否を行うための期待多項式時間アルゴリズムが得られる。逆に、チューリングマシンが（任意の x に対して）期待多項式時間である場合、実行のかなりの割合が多項式時間で制限されなければならず、そのような実行で使用されるコインのシーケンスが証拠となる。
ZPPはBPPと対比されるべきである。BPPクラスは証拠を必要としないが、証拠は十分である（したがって、BPPはRP、co-RP、およびZPPを含む）。BPP言語では、xがXに含まれる場合、文字列wの（明確な）過半数に対してV(x,w)が受理され、逆にxがXに含まれない場合、文字列wの（明確な）過半数に対して拒否される。単一の文字列wが決定的なものである必要はなく、したがって一般に証明または証拠とみなすことはできない。
ZPPは補集合に関して閉じている、つまりZPP = co- ZPPである（これはZPP = RP ∩ co- RPから導かれる）。
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となるオラクルが存在する。[ 1 ] ZPP = EXPTIMEの証明は、 P ≠ EXPTIMEであることから、P ≠ ZPPを意味する（時間階層定理を参照）。