証拠と証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 03:55 UTC 版)
クラス NP、RP、ZPP は、ある集合のメンバーシップの証明の手段と考えることもできる。 定義: 集合 X についての検査器 V は以下のようなチューリング機械であるとする。 x が X に含まれる場合、ある文字列 w が存在し V(x,w) は受理される。 x が X に含まれない場合、あらゆる文字列 w について V(x,w) は受理されない。 文字列 w はメンバーシップの証明と考えることができる。証明が短い（入力長の多項式で表される長さ）なら、（V は多項式時間の決定性チューリング機械なので）効率的な検査が可能であり、その文字列 w を「証拠; witness」と呼ぶ。 注記: この定義は非対称である。x が X に含まれることの証明には1つの文字列があればよい。x が X に含まれないことの証明には、メンバーシップの証明ではない全文字列の集合が必要となる。 証拠の入手可能性は一様である。X に含まれる全ての x には必ず証拠が対応している。特定の x について検証が難しく、他はそうでないという話ではない。 証拠はいわゆる古典的な意味での証明である必要はない。V が X に属する x を受理する確率的チューリング機械だった場合、証明はコイントスのような文字列であり、運がよければ x を受理することになる。 その補概念は、非メンバーシップの証明か、補集合のメンバーシップの証明となる。 クラス NP、RP、ZPP はメンバーシップの証拠を持つ集合である。NP はそのような証拠が存在しさえすればよい。これは非常に珍しい。2f(|x|) 個の文字列のうち（f()は多項式）、1つの文字列だけが検査器に受理される（x が X に含まれる場合。そうでない場合、どの文字列も受理されない）。 クラス RP と ZPP では無作為に選んだ文字列が証拠となりうる。 対応する補問題のクラスは非メンバーシップの証拠を持つ。特に Co-RP は、x が X に含まれない場合、無作為に選んだ文字列が非メンバーシップの証拠となりうる集合のクラスである。ZPP は無作為に選んだ文字列がメンバーシップの証拠にも非メンバーシップの証拠にもなりうる集合のクラスである。 この定義と RP、Co-RP、ZPP の通常の定義を結びつけるのは容易である。確率的多項式時間チューリング機械 V*w(x) を決定性多項式時間チューリング機械 V(x,w) と対応させるには、V* の乱数テープを V の第二のテープにコイントスの列を書き込んだものと置き換えればよい。証拠選択を乱数列とすることで検査器は確率的チューリング機械となり、x が X に含まれるときにそれを受理する確率は大きく（1/2以上）、X に含まれないときに受理する確率はゼロとなる（RPの場合）。あるいは、x が X に含まれないとき受理しない確率は大きく、X に含まれるときに受理しない確率はゼロとなる（Co-RPの場合）。あるいはまた、受理・不受理を正しく行う確率は大きく、不正に受理・不受理する確率はゼロとなる（ZPPの場合）。 可能な証拠を無作為選択することを繰り返すと、大きな確率で無作為文字列が証拠となって受理・不受理を決定する多項式時間アルゴリズムになる。逆にチューリング機械が多項式時間で完了するなら、その処理の大部分は多項式時間内に制限され、そこで使われたコイントスの列は証拠となる。 ZPP は BPP と対比させられる。BPP は証拠を必要としないが、証拠があれば十分である（従って、BPP は RP も Co-RP も ZPP も包含する）。BPP言語の V(x,w) は x が X に含まれるなら大部分の文字列 w で受理され、x が X に含まれないなら大部分の文字列 w で不受理となる。特定の文字列 w が必要とはされない。従って、一般に証明とも証拠とも見なされない。
※この「証拠と証明」の解説は、「ZPP」の解説の一部です。
「証拠と証明」を含む「ZPP」の記事については、「ZPP」の概要を参照ください。
- 証拠と証明のページへのリンク
