5

NP 困難な問題について混乱しています。
NP 困難な問題には、NP 完全と呼ばれる NP に含まれるものと、NP に含まれないものがあります。
例 : 停止問題は NP 困難であり、NP 完全ではありません。
しかし、なぜNP完全ではないのでしょうか?
問題が「NP困難だがNP完全ではない問題」と見なされるには、どのようなプロパティが必要ですか?

4

4 に答える 4

3

最短の答えは、NP-complete = NP-hard AND in NP だと思います。

したがって、ある問題が NP 完全であることを示すには、それが NP 困難であると同時に NP であることを示す必要があります。通常、問題が NP にあることを示すのは非常に簡単です (非決定論的多項式時間アルゴリズムを与えるだけです)。問題が NP 困難であることを示すことは、まあ、難しいことです。したがって、NP完全性の証明であっても、ほとんどの証明は NP硬度に専念しています。

停止問題に関しては、NP にならないため、NP 完全ではありません。

于 2011-04-14T18:08:23.423 に答える
2

NP を定義するのは、多項式時間で NP 問題の解を検証できるという事実です。したがって、問題が NP 困難であるが NP 完全ではない場合、問題の解決策を理論的にタイムリーに検証することはできません。停止問題を見れば、これは理にかなっています。解決策は「はい」または「いいえ」のいずれかであり、元の問題を再度解決することによってのみ確認できます。つまり、NP にはありません。

于 2012-08-08T12:29:41.033 に答える
1

NP-hard は単に「少なくとも NP の問題と同じくらい難しい」という意味です。NP完全とは、「NPでは、すべてのNP完全問題はこの問題に還元でき、この問題はすべてのNP完全問題に還元できる」という意味です。

ウィキペディアの記事は、その例の 1 つとして停止問題について具体的に述べているため、おそらく良い出発点です。

于 2011-04-14T11:46:35.720 に答える
0

簡単な答え: NP 完全ではない唯一の NP 困難な問題は、NP の一部ではない問題です。

長い答え:

さて、それはなぜですか？NP 完全と NP 困難の定義を注意深く見てみましょう。

次の場合、問題 X は NP 完全です。

  1. NPにある

  2. NP のすべての問題は、多項式時間で X に還元可能です。

問題 X が (2) を満たす場合、問題 X は NP 困難です ((1) は必要条件ではありません)。

これらの定義から、NP 困難であるが NP 完全ではない唯一の問題は、NP から外れたものであると結論付けることは明らかです。

たとえば、決定問題ではないすべての NP 困難な問題は NP 完全ではありません (定義による NP は決定問題で形成されるため)。特に、巡回セールスマン問題の検索バージョン:都市のリストとそれらのペアごとの距離が与えられた場合、タスクは、各都市を 1 回だけ訪れて元の都市に戻る最短ルートを見つけることです。

TSP の検索バージョンは NP 困難であることが証明されていますが、これは決定問題ではないため (質問に「はい」または「いいえ」で答えることはできません)、NP の一部ではないため、NP 完全にすることはできません。

停止問題は決定問題ですが、ポリモニアル時間 (定義により問題が NP であるという 2 番目の要件) で検証できないため、NP 完全にすることはできません。

于 2013-02-18T00:55:38.367 に答える