複雑さ理論における「決定」と「検証」の違いは何ですか？

Question

マイケル・シップサーの 計算理論 270ページに、彼は次のように書いています。

p =メンバーシップを迅速に決定できる言語のクラス。
NP =メンバーシップを迅速に検証できる言語のクラス。

「決定」と「検証」の違いは何ですか？

Answer 1

のタスク 決定 メンバーシップは次のとおりです。入力$ x $、l $ in wether $ x in l $を決定する、つまり、次の関数を計算します。

$ qquad displaystyle chi_l（x）= begin {cases} 1＆x in l 0＆x notin l end {cases} $

一方、のタスク 検証 メンバーシップは次のとおりです：入力$ x $とa（提案） 証拠 （また 目撃者）メンバーシップの場合、$ x in l $をすばやくチェックしてください その証拠によって¹.

たとえば、素数の要因を検討してください。 $ n in mathbb {n} $が与えられた場合、$ n $のすべての素数を計算します。一方、$（n、 {i_1、 dots、i_k }）$が与えられ、$ prod_ {j = 1}^k i_j = n $を確認します。どちらが簡単ですか？

別の例：加重グラフ$ g =（v、e）$が与えられた場合、最大$ k $の重量のあるハミルトンサークル（すべてのノードにアクセス）がある場合に決定します。一方、$（g、（v_1、 dots、v_n））$が与えられた場合、パス$ v_1 to dots to v_n $を確認してください。どちらが難しいですか？

---

1. したがって、$ x in l $であるが、証明が間違っている場合、「いいえ」と言うでしょう。ただし、このコンテキストでは非決定的機械を検討するため、それは問題ありません。できることだけが重要です 推測してみて 正しい証明と検証（すばやく）。

Answer 2

効率の問題を無視すると、類推による違いを示す別の例があります。停止問題は決定できないことを知っています。チューリングマシンのコード$ e $を考えると、入力なしで実行されている場合にマシンが停止するかどうかを判断する効果的な方法はありません。

しかし、マシンの場合 します 停止すると、他の人に証明するのは難しくありません。停止する前にマシンが実行するステップ数を伝えてください。彼らはその多くのステップのためにマシンを実行し、あなたが真実を語ったかどうかを知ることができます（もちろん、効率を無視します）。

したがって、チューリングマシンを停止するセットは決定できませんが、検証可能です。マシンに証明を与えなければならないことに注意してください しないでください 停止。検証は、メンバーシップのみであるという意味で非対称です の セットには、検証可能なメンバーシップがあります アウト セットのものはありません。

PとNPの状況は類似しています。各オブジェクトがそうであるような証明のシステムがある場合、言語はNPにあります の 言語には、効率的に検証できる短い証明（オブジェクトのサイズの多項式に囲まれています）があります（入力のサイズの多項式で囲まれた多くのステップを使用）。

一方、任意のオブジェクトがオブジェクトのサイズの多項式に囲まれたいくつかのステップを使用して言語にあるかどうかを判断する方法がある場合、言語はPにあります。ここで、言語のオブジェクトだけでなく、任意の入力について心配する必要があります。しかし、この問題は対称です。言語がpにある場合、その補完もそうです。すべてのNP言語の補完がNP言語であるかどうかの質問は未解決です。

（この類推は、NPの問題が再セットのようなPの問題であることを示唆しています。それはやや真実ですが、誤解を招く可能性があります。これは、REとCO-REのセットが計算可能であり、一方NPおよびCO-NPであるすべてのセットがp）にあるかどうかは不明です。