31

私の理解では、すべての NP 完全問題は NP 困難ですが、一部の NP 困難問題は NP 完全ではないことが知られており、NP 困難問題は少なくとも NP 完全問題と同じくらい困難です。

それは、NP完全ではないNP困難な問題がより困難であることを意味しますか? そして、それはどのように難しいですか？

4

6 に答える 6

23

この質問に答えるには、まずどの NP 困難問題が NP 完全でもあるかを理解する必要があります。NP 困難な問題が集合 NP に属している場合、それは NP 完全です。集合 NP に属するためには、問題が

(i) 決定問題、
(ii) 問題の解の数は有限で、各解は多項式の長さ、
(iii) 多項式の長さの解が与えられると、問題ははい/いいえです

ここで、集合 NP に属さず、解くのが難しい多くの NP 困難な問題が存在する可能性があることは簡単にわかります。直感的な例として、実際のスケジュールを見つける必要がある巡回セールスマンの最適化バージョンは、長さ <= k のスケジュールが存在するかどうかを判断するだけでよい巡回セールスマンの決定バージョンよりも困難です。

于 2011-06-18T16:41:47.110 に答える
10

チューリング マシンの停止問題は、チューリング マシンと NP ハードでは決定できませんが、NPC では決定できません。どうやらそれは難しいです;）

于 2011-06-19T05:18:30.263 に答える
6

チューリング停止問題は決定不能であり、NP困難セットに属します。停止性問題を解決するために、それはRE言語であるため、決定者はありません。したがって、それを解決するためのアルゴリズムはありません。したがって、解決できない問題がNP困難セットにもあることは明らかです。したがって、NP困難セットには、解決するアルゴリズムがない言語または問題も含まれています。

于 2012-09-10T14:20:32.770 に答える
6

NP 困難な問題のセットは、NP 完全問題のセットのスーパーセットです。PSPACE、EXPTIME、EXPSPACEなど、NP よりも「難しい」複雑さのクラスがあり、これらすべてに NP 困難な問題が含まれていますが、NP 完全な問題は含まれていません。

于 2010-10-14T11:06:02.217 に答える
2
  1. NP完全はNPおよびNP困難でなければなりません。
  2. NP完全ではないNP困難はNPではありません。
  3. 現在、NPの定義により、問題の回答インスタンスを提供する人がいます。検証するベリファイアがあります。
  4. これは、NP困難がどちらも持っていないことを意味します。したがって、それらを解決するのは困難です。
于 2012-12-12T07:16:56.870 に答える
2

http://en.wikipedia.org/wiki/NP-hard#Examplesから

停止問題など、NP 困難であるが NP 完全ではない決定問題もあります。これは、「プログラムとその入力が与えられた場合、それは永遠に実行されますか?」という問題です。これははい/いいえの質問なので、これは意思決定の問題です。停止問題が NP 困難であるが NP 完全ではないことを証明するのは簡単です。

于 2010-09-28T05:35:01.557 に答える