将 SAT 降低到 HALT
Reduce SAT to HALT
我们如何将布尔 SAT 问题简化为 HALTING 问题？我试过了，但不知道如何开始。
最后，我想证明HALT是NP-HARD，那么有没有比这更好的方法来证明HALT是NP-HARD？
基本上，我们可以假设一个考虑所有可能分配的图灵机：
- 如果找到满意的分配，则机器停止
- 否则一直循环
如果找不到令人满意的分配，则它将永远运行。当且仅当 3SAT 实例可满足时，该机器才会停止。给定 3SAT 的输入 F（3Sat 公式），我们将输入传递给 HALT(M, F) 并查看答案是什么。
我们如何将布尔 SAT 问题简化为 HALTING 问题？我试过了，但不知道如何开始。
最后，我想证明HALT是NP-HARD，那么有没有比这更好的方法来证明HALT是NP-HARD？
基本上，我们可以假设一个考虑所有可能分配的图灵机：
- 如果找到满意的分配，则机器停止
- 否则一直循环
如果找不到令人满意的分配，则它将永远运行。当且仅当 3SAT 实例可满足时，该机器才会停止。给定 3SAT 的输入 F（3Sat 公式），我们将输入传递给 HALT(M, F) 并查看答案是什么。