28

NP、NP-hard、および NP-complete の定義に関するこの質問への回答で、Jason は次のように主張しています。

停止問題は古典的な NP 困難問題です。これは、プログラム P と入力 I が与えられた場合、停止するかという問題です。これは決定問題ですが、NP にはありません。あらゆる NP 完全問題がこの問題に還元できることは明らかです。

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

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

4

1 に答える 1

45

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

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

于 2011-08-09T02:12:50.380 に答える