スタンフォード大学の Tim Roughgarden 教授は、MOOCを教えているときに、クラス NP の問題の解は長さが多項式でなければならないと述べました。しかしウィキペディアの記事によると、NP 問題は決定問題です。では、クラス NP には基本的にどのような種類の問題があるのでしょうか? また、そのような問題の解には多項式の長さの出力があると言う必要はありません (決定問題は必ず 0 または 1 を出力するため) ?
質問する
1024 次
3 に答える
4
彼はおそらく目撃者と検証者について話していました。
NPのすべての問題に対して、多項式時間で「はい」の主張を検証できる検証者（読み取りアルゴリズム/チューリングマシン）があります。
アイデアは、時間の制約を考慮してこれを行うのに役立つある種の情報（証人）を持っているということです。
たとえば、巡回セールスマン問題では、次のようになります。
TSP = {(G, k) if G has a hamiltonian cycle of cost <= k}
特定の入力（G、k）について、問題のインスタンスがTSPにあるかどうかを判断するだけで済みます。それはイエス/ノーの答えです。
ここで、誰かがやって来て次のように言った場合：この問題のインスタンスはTSPにあり、証明を要求します。他の人はおそらくあなたに一連の都市を与えるでしょう。次に、その順序の都市がハミルトン閉路を形成しているかどうか、およびサイクルの総コストが≤kであるかどうかを簡単に確認できます。
証人の長さが多項式である場合、この手順は多項式時間で実行できます。
したがって、この一連の都市を使用して、問題のインスタンスが実際にTSPにあることを正しく判断することができました。
これが検証者の考え方です。検証者は、特定の問題インスタンスが言語にあることを確認するために、長さが多項式である証明オブジェクト/証人を取得します。
于 2013-02-10T17:18:21.783 に答える
2
NP の標準的な定義は、NP は決定問題のみのクラスであるというものです。意思決定問題は常に yes/no の答えを生成するため、一定サイズの出力が得られます。
于 2013-02-10T15:41:44.550 に答える
1
ビデオ/コースは見ていませんが、彼はソリューションではなく証明書/検証について話していたと思います。大きな違い。
于 2013-02-10T16:18:36.580 に答える