theory - 证明停止问题是 NP 难的？

Question

在这个关于 NP、NP-hard 和 NP-complete 定义的问题的回答中，Jason 声称

停止问题是经典的 NP-hard 问题。这是给定程序 P 和输入 I 的问题，它会停止吗？这是一个决策问题，但它不在 NP 中。很明显，任何 NP 完全问题都可以简化为这个问题。

虽然我同意停机问题在直觉上是一个比 NP 中的任何问题都“更难”的问题，但老实说，我无法提出一个正式的数学证明来证明停机问题是 NP 难的。特别是，我似乎无法找到从 NP 中的每个问题（或至少任何已知的 NP 完全问题）的实例到停止问题的多项式时间多对一映射。

是否有直接的证据证明停机问题是 NP 难的？

Answer 1

我们首先注意到所有 NP 完全问题都可以简化为 3SAT。现在我们有了一个图灵机，它遍历所有可能的分配，如果没有找到令人满意的分配，它就会永远运行。当且仅当 3SAT 实例可满足时，此机器才会停止。

完成证明——我们可以在多项式时间内将 NP 完全问题的任何实例简化为 3SAT。从那里，我们可以通过将输入与上述图灵机的描述（具有恒定大小）配对，将这个问题简化为停机问题的一个实例。这种配对可以在多项式时间内完成，因为图灵机只有恒定的大小。然后，如果图灵机在给定输入上停止，则如果 3SAT 实例可满足，则原始 NP 完全问题的答案为“是”。