We begin by noting that all NP-complete problems are reducible to 3SAT. Now we have a Turing machine that iterates over all possible assignments, and if a satisfying assignment is not found then it runs forever. This machine halts if and only if the 3SAT instance is satisfiable.
Completing the proof - we can, in polynomial time, reduce any instance of an NP-complete problem to 3SAT. From there, we can reduce this problem to an instance of the halting problem by pairing the input with a description of the Turing machine described above (which has constant size). This pairing can be done in polynomial time, because the Turing machine has only constant size. Then, the original NP-complete problem has answer "yes" iff 3SAT instance is satisfiable iff the Turing machine halts on the given input.
发布评论
评论（1）
我们首先注意到所有 NP 完全问题都可以简化为 3SAT。现在我们有一个图灵机，它会迭代所有可能的分配，如果找不到令人满意的分配，那么它会永远运行。当且仅当 3SAT 实例可满足时，该机器才会停止。
完成证明——我们可以在多项式时间内将 NP 完全问题的任何实例减少到 3SAT。从那里，我们可以通过将输入与上述图灵机的描述（具有恒定大小）配对来将此问题简化为停止问题的实例。这种配对可以在多项式时间内完成，因为图灵机只有恒定的大小。然后，当且仅当 3SAT 实例可满足当且仅当图灵机在给定输入上停止时，原始 NP 完全问题的答案为“是”。
We begin by noting that all NP-complete problems are reducible to 3SAT. Now we have a Turing machine that iterates over all possible assignments, and if a satisfying assignment is not found then it runs forever. This machine halts if and only if the 3SAT instance is satisfiable.
Completing the proof - we can, in polynomial time, reduce any instance of an NP-complete problem to 3SAT. From there, we can reduce this problem to an instance of the halting problem by pairing the input with a description of the Turing machine described above (which has constant size). This pairing can be done in polynomial time, because the Turing machine has only constant size. Then, the original NP-complete problem has answer "yes" iff 3SAT instance is satisfiable iff the Turing machine halts on the given input.