在回答一个关于NP、NP-hard和NP-complete定义的问题时，Jason断言
停机问题是典型的np困难问题。这个问题是给定程序P和输入I，它会停止吗?这是一个决策问题，但不是NP问题。很明显，任何np完全问题都可以简化为这个问题。
虽然我同意暂停问题在直觉上是一个比NP中的任何问题都"更难"的问题，但老实说，我无法提出一个正式的、数学的证明来证明暂停问题是NP困难的。特别是，我似乎找不到一个多项式时间的多对一映射，从NP中的每个问题(或至少，任何已知的NP完全问题)的实例到停止问题。
是否有一个直接的证据证明暂停问题是np困难的?
我们首先注意到所有np完全问题都可约化为3SAT。现在我们有一个图灵机，它遍历所有可能的赋值，如果没有找到一个满意的赋值，它就会永远运行下去。当且仅当3SAT实例满足时，此机器停止。
完成证明-我们可以在多项式时间内，将np完全问题的任何实例简化为3SAT。从那里，我们可以通过将输入与上面描述的图灵机的描述配对(它具有恒定的大小)，将这个问题简化为停机问题的一个实例。这种配对可以在多项式时间内完成，因为图灵机只有常数大小。那么，当图灵机在给定输入上停止时，如果3SAT实例是可满足的，则原np完全问题的答案为"是"。