减少SAT停止

Question

如何将布尔SAT问题归结为停止问题？我试过了，但不知道怎么开始。

最后，我想证明this是NP-HARD，那么有比这个更好的方法来证明this是NP-HARD吗？

Answer 1

基本上，我们可以假设图灵机器考虑所有可能的任务：

• 如果找到令人满意的任务，机器将停止工作。
• 否则，它会永远循环。

如果找不到令人满意的任务，那么它将永远运行。该机器停止当且仅当3 3SAT实例是可满足的。给定输入F (3 3SAT公式)到3 3SAT，我们将输入传递给 what (M，F)，看看答案是什么。