在这个答案中，对于有关 NP、NP-hard 和 NP-complete 定义的问题，Jason 声称
停止问题是经典的 NP 难问题。这就是给定程序 P 和输入 I 的问题，它会停止吗？这是一个决策问题，但不属于 NP 问题。很明显，任何 NP 完全问题都可以简化为这个问题。
虽然我同意停机问题直观上比 NP 中的任何问题都“难”得多，但老实说我无法提出正式的数学证明来证明停机问题是 NP 难问题。特别是，我似乎无法找到从 NP 中每个问题的实例（或者至少是任何已知的 NP 完全问题）到停止问题的多项式时间多对一映射。
是否有直接的证据证明停止问题是 NP 困难的？
我们首先注意到所有 NP 完全问题都可以简化为 3SAT。现在我们有一个图灵机，它会迭代所有可能的分配，如果找不到令人满意的分配，那么它会永远运行。当且仅当 3SAT 实例可满足时，该机器才会停止。
完成证明——我们可以在多项式时间内将 NP 完全问题的任何实例减少到 3SAT。从那里，我们可以通过将输入与上述图灵机的描述（具有恒定大小）配对来将此问题简化为停止问题的实例。这种配对可以在多项式时间内完成，因为图灵机只有恒定的大小。然后，原始 NP 完全问题的答案是“是”，当且仅当 3SAT 实例可满足当且仅当图灵机在给定输入上停止时。
在给定的文本中，“这个问题”是特指 3SAT 问题还是任意 NP 问题？ “从那里，我们可以通过将输入与上述图灵机的描述（具有恒定大小）配对来将此问题简化为停止问题的实例。”