来自NP-Complete的维基百科条目:
"证明一些新问题是NP完全的最简单的方法是首先证明它是在NP中,然后减少一些已知的NP完全问题"
我很确定我理解这一点:如果我有问题,我可以证明它是NP-Complete如果我:
表明它在NP中(可以在非确定性图灵机上的多项式时间内验证问题的解决方案)
表明已知为NP-Complete的问题可以"减少"到新问题
所以,我的问题是,第一个NP完全问题"被证明"是NP完全的吗？同时,已知NP完全问题的集合必须为零,这将使得在上述过程中不可能采用步骤2.
这让我觉得有一种不同的证明方法,我不知道.由于缺少已知的多项式时间解决方案,或者可能由于缺少已知的多项式时间解而对某些问题"假设"整个NP完全属性.(实际上,写完这篇文章后,如果是这样的话,我不会感到惊讶,但无论如何我都喜欢一些古茹反馈).
库克定理
NP类可以定义为在多项式时间内由非确定性图灵机可判定的问题类别.该定理通过布尔公式对任何非确定性图灵机的操作进行编码,表明SAT是NP完全的,这样机器只有在该公式满足时才接受.
从历史上看,NP完全性的概念是在理查德卡普的开创性论文(组合问题中的可约性)中引入的,他在这篇论文中定义了NP完全性,使用了库克定理,并在一个大的镜头中证明了21个问题NP完全.
京公网安备 11010802040832号 | 京ICP备19059560号-6 