停止問題はNP困難ですか？

Question

（これはこの質問のサイトが間違っている場合は謝りますが、ここではCS理論の質問がたくさんあることを謝りますが、これは適切かもしれません。NP、NP困難の定義についての質問にthis answerで）。

を、それは不適切だ場合は、これを移動すること自由に感じなさい、とNP完全、ジェイソンはその

請求停止問題になります古典的なNPハードの問題です。これは、プログラムPと入力Iを与えられた場合、それは停止するのでしょうか？これは決定の問題ですが、NPにはありません。これはNP完全な問題がこの問題に還元できることは明らかです。

停止問題は直感的にNPの何かよりも「難しい」問題であると私は同意しますが、停止問題がNP困難であるという正式な数学的証明を正直に思い出すことはできません。特に、NP中のすべての問題のインスタンス（または少なくとも既知のNP完全問題）から停止問題に多項式時間の多対1のマッピングを見つけることはできないようです。

停止問題がNP困難であるという簡単な証拠はありますか？

Answer 1

すべてのNP完全問題が3SATに還元されることに注意してください。今度はすべての可能な割り当てを繰り返すチューリングマシンがあり、満足のいく割り当てが見つからなければ、それは永遠に実行されます。このマシンは、3SATインスタンスが充足可能である場合にのみ停止します。

証明の完成 - 多項式時間で、NP完全問題のインスタンスを3SATに減らすことができます。そこから、入力を上記のチューリングマシンの記述（一定のサイズを持つ）とペアにすることで、この問題を停止問題のインスタンスに減らすことができます。チューリングマシンは一定の大きさしか持たないので、このペアリングは多項式時間で行うことができます。そして、元のNP完全問題は、与えられた入力に対してチューリング機械が停止した場合に3SATインスタンスが充足可能である場合に、「はい」と答えている。