NP-complete対NP-hard（なぜそれらは等しくないのですか）

Question

なぜNP-hardはNP-completeと等しくないのですか？使用されている定義の

私の非公式の理解：

NP - 多項式時間で検証することができるすべての問題

NP完全 - NPとNP-ハード

あるすべての問題NP-hard - NPの最も難しい問題と同じくらい難しいです。

Decision Problem - 入力に関して質問をしてブール値を出力する問題

混乱：

NP対Pの未知の解決策の問題は、我々はNPのすべての問題は多項式時間で解くことができることを証明または反証できないという事実から生じます。それは、同様の質問がNP完全対NP困難から生じるように感じる。 NP-hardのすべての問題が多項式時間で検証できないため、NP-hard = NP-completeとなることをどのように知っていますか？ここで

はオンライン研究から推論の私のライン

で区別は、これは決定問題（私はに全く新しいですが、十分に単純なように見えるコンセプト）とは何かを持っているようです。 NPの問題には、入力が問題の解決策であるかどうかを尋ねる相補的な決定問題があることを意味します。問題が最適な解決策を見つけることであるとしましょう。私は補完的決定問題は「与えられた入力は最適解である」と信じています。この決定問題が多項式時間で検証可能ならば、問題はNP完全（またはNP）です。これは、NP完全な問題ではないNP困難な問題は、決定的な問題がないか（ブルートフォース解決策がこれに答えることができないので決して真実ではない）、または問題はNP困難でNPではない - 多項式時間で検証できない決定問題がある場合は、それを完成させます。後者の場合は、P対NPと同じ問題があるように感じます。つまり、NP-hardのすべての決定問題に多項式時間解がないことを確認するにはどうすればよいでしょうか？

申し訳ありませんが、上記の表現が奇妙です。私は私の質問の混乱を明確にしようとします。

ノート

私は直感的な説明と、正式な説明（それは複雑な答えだ場合の証明）の両方に興味を持っています。正式な説明は、確かに学術論文へのリンクとなりうる。私は誰もが私の理解の範囲を超えているかもしれない過度に複雑な証拠にかなりの時間を投資することを望んでいません（複雑な理論が非常に迅速に複雑になることがわかりました...複雑です）。

説明のために役立つ場合、私は旅行セールスマンの問題に取り組んできました。現在、私は看護師のスケジューリングの問題に関するペーパーを作成しています（これはNP困難な問題だと思います）。

Answer 1

NP-Hardには、多項式オーバーヘッドを持つNPの問題の解を導出するためにその解を使用できるすべての問題が含まれています。

これは、がNPにない多くの問題を含んでいます。例えば、停止問題 - 決定不能問題 - NPのいずれかの問題が多項式時間でそれに減少させることができるので、NP-ハードです：

1. はNP完全問題のインスタンスにNPのいずれかの問題を軽減します3-SAT
2. すべての代入をチェックし満足する代入が見つかると停止するTMを多項式時間で構築します。
3. 停止問題の解決策を使用して、TMが停止しているかどうかを確認します。
4. 停止する場合は受け入れます。それ以外の場合は拒否します