证明暂停问题是NP
（对于这个问题，如果这是错误的网站，我表示歉意，但鉴于这里有很多“CS理论不足够”的CS理论问题，我认为这可能是一个不错的选择。如果不合适，请随时提出。）
在这个关于NP，NP-hard和NP-complete的定义问题的答案中，Jason提出了这个观点
暂停问题是经典的NP难题。 这是给定程序P和输入I的问题，它会停止吗？ 这是一个决策问题，但它不在NP中。 很明显，任何NP完全问题都可以归结为这个问题。
尽管我同意暂停问题在直觉上是一个比NP更难的“更难”问题，但我实际上不能拿出一个正式的数学证明来证明暂停问题是NP难题。 特别是，我似乎无法从NP中的每个问题的实例（或者至少是任何已知的NP完全问题）中找到一个多项式时间多对一映射到停止问题上。
有没有一个直截了当的证据表明暂停问题是NP-hard？
我们首先注意到所有NP完全问题都可以归结为3SAT。 现在我们有了一个图灵机，它遍历所有可能的任务，如果没有找到满意的任务，那么它将永远运行。 当且仅当3SAT实例可满足时，此机器才会停止。
完成证明 - 我们可以在多项式时间内将任何NP完全问题的实例减少到3SAT。 从那里，我们可以通过将输入与上述图灵机器的描述（具有恒定大小）配对来将此问题减少为停机问题的一个实例。 这种配对可以在多项式时间内完成，因为图灵机只有恒定的尺寸。 然后，如果图灵机停止在给定的输入上，如果3SAT实例可满足，则原始的NP完全问题回答“是”。
链接地址: http://www.djcxy.com/p/39981.html