ZPP (複雑さ)

複雑性理論において、ZPP (ゼロエラー確率多項式時間) は、以下の特性を持つ確率的チューリング マシンが存在する問題の複雑性クラスです。

• 常に正しい YES または NO の回答を返します。
• 実行時間は、すべての入力に対して期待値の多項式です。

言い換えれば、アルゴリズムの実行中に完全にランダムなコインを投げることが許されていれば、アルゴリズムは常に正しい答えを返し、サイズnの問題に対して、平均実行時間がp ( n ) より短くなるような多項式p ( n ) が存在します。ただし、場合によってはそれより長くなることもあります。このようなアルゴリズムはラスベガス アルゴリズムと呼ばれます。

あるいは、ZPP は、次の特性を持つ確率的チューリング マシンが存在する問題のクラスとして定義することもできます。

• 常に多項式時間で実行されます。
• YES、NO、またはDO NOT KNOWという回答を返します。
• 答えは常に「分からない」か「正解」のいずれかです。
• すべての入力に対して最大 1/2 の確率で DO NOT KNOW を返します (それ以外の場合は正しい回答を返します)。

2つの定義は同等です。

ZPPの定義は確率的チューリングマシンに基づいていますが、明確にするために、それらに基づく他の複雑性クラスにはBPPとRP が含まれることに注意してください。クラスBQP は、ランダム性を備えた別のマシン、量子コンピュータに基づいています。

クラス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交差co-RPに含まれることを示すために、問題を解決するためのラスベガス アルゴリズム C があると仮定します。次に、次のRPアルゴリズムを構築できます。

• C を予想される実行時間の少なくとも2 倍実行します。答えが返ってきたら、その答えを返します。停止する前に答えが返ってこない場合は、NO を返します。

マルコフの不等式により、停止する前に答えが出る可能性は少なくとも 1/2 です。つまり、停止して NO を出すことによって YES インスタンスで間違った答えを出す可能性は最大で 1/2 であり、RPアルゴリズムの定義に適合します。co -RPアルゴリズムは、C が「タイムアウト」した場合に YES を出す点を除いて同一です。

クラスNP、RP、ZPP は、集合内のメンバーシップの証明という観点から考えることができます。

定義:集合 X の 検証者Vは次のようなチューリング マシンです。

• x がXに含まれる場合、 V ( x、w ) が受け入れる文字列w が存在する。
• xがXに含まれない場合、すべての文字列wに対して、V ( x , w ) は拒否されます。

文字列w はメンバーシップの証明と考えることができます。効率的に検証できる短い証明 (長さが入力のサイズの多項式で制限される) の場合 ( Vは多項式時間の決定論的チューリングマシン)、文字列wは証人と呼ばれます。

注:

• 定義は非常に非対称です。x が X に含まれることの証明は単一の文字列です。x が X に含まれないことの証明はすべての文字列の集合であり、そのどれもがメンバーシップの証明ではありません。
• X 内のすべての x については、それが X に属していることの証拠がなければなりません。
• 証人は、伝統的に解釈された証明である必要はありません。V が、x が 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*のランダムテープを、コイン投げのシーケンスが書き込まれた V の 2 番目の入力テープに置き換えることで、決定論的多項式時間チューリングマシンV ( x、w )に対応します。証人をランダム文字列として選択することで、検証者は確率多項式時間チューリングマシンになり、 x がXにある場合に x を受け入れる確率は大きくなり (たとえば、1/2 より大きい)、x ∉ Xの場合は 0 になります( RPの場合)。 x が X にない場合に x を拒否する確率は大きくなりますが、x ∈ Xの場合は 0 になります( co-RPの場合)。 x をXのメンバーとして正しく受け入れるまたは拒否する確率は大きくなりますが、 x を誤って受け入れるまたは拒否する確率は 0 になります ( 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 はそれ自体が低いため、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 ≠ EXPTIMEであるため、P ≠ ZPPであることを意味します(時間階層定理を参照)。

• ＢＰＰ
• RP

• 複雑性動物園: ZPP クラス ZPP