tem*_*def 21 theory proof halting-problem np
在这个关于NP,NP-hard和NP-complete定义的问题的答案中,Jason提出了这样的主张
停止问题是经典的NP难问题.这是给出程序P和输入I的问题,它会停止吗？这是一个决策问题,但它不在NP中.很明显,任何NP完全问题都可以简化为这个问题.
虽然我同意停止问题在直觉上比NP中的任何问题都要困难得多,但老实说,我无法提出一个正式的数学证明,即停止问题是NP难的.特别是,我似乎无法找到从NP(或至少任何已知的NP完全问题)中的每个问题的实例到停止问题的多项式时间多对一映射.
是否有一个直截了当的证据表明停止问题是NP难的？
小智 36
我们首先注意到所有NP完全问题都可以简化为3SAT.现在我们有一个图灵机可以迭代所有可能的任务,如果找不到令人满意的任务,那么它就会永远运行.当且仅当3SAT实例可满足时,此机器才会停止.
完成证明 - 我们可以在多项式时间内将NP完全问题的任何实例减少到3SAT.从那里,我们可以通过将输入与上述图灵机的描述(具有恒定大小)配对,将该问题减少到停止问题的实例.这种配对可以在多项式时间内完成,因为图灵机只有恒定的尺寸.然后,如果图灵机停止在给定输入上,如果3SAT实例是可满足的,则原始NP完全问题已回答"是".