假设P = NP证明是什么样的？

Question

它是一个特定NP完全问题的多项式时间算法,还是仅仅是抽象推理能够证明存在NP完全问题的解决方案？

似乎特定的算法更有帮助.有了它,我们要多方面地解决NP问题所需要做的就是将它转换成证明有解决方案的特定NP完全问题,我们就完成了.

Answer 1

P = NP:" 3SAT问题是一个经典的NP完全问题.在这个证明中,我们演示了一个解算它的算法,它具有渐近界限(n ^ 99 log log n).首先我们......"

P!= NP:"假设有一个多项式算法用于3SAT问题.这意味着....这意味着我们可以做......然后......然后......这是不可能的.这都是基于3SAT的多项式时间算法.因此P!= NP."

更新:也许像这篇论文(P!= NP).

@dbr我发现了一个真正奇妙的证据,这个评论太狭隘了.:) (29认同)
所有NP完全问题都在多项式时间内减少到每个其他NP完全问题.因此,任何这些问题的证据就足够了. (9认同)
这足以证明例如3SAT没有多项式时间算法.然后对于任何其他NP完全问题X,3SAT是多项式时间可简化为X,因此如果X具有多项式时间算法,则3SAT将有一个减少到X.请参阅http://en.wikipedia.org/wiki/NP完全#Formal_definition_of_NP,完整性 (7认同)
你知道,如果你只是填写"...",那么你可以很容易地获得最受欢迎的SO答案! (6认同)

Answer 2

叫我悲观,但它会是这样的:

...

∴,P≠NP

QED

Answer 3

还有一些荟萃结果是有关一个P = NP或P≠NP证明可以不样子.细节非常技术性,但众所周知,证明不可能

相对化,这种意味着该证明必须利用使用图灵机的确切定义的,因为有一些修改("预言",像非常强大的CISC指令添加到指令集)P = NP,并与一些其它的修改,P≠NP.另请参阅此博客文章,了解相对化的一个很好的解释.
自然,几个经典电路复杂性证明的属性,
或相似的,相对化的概括.

Answer 4

它可以采取证明假设P≠NP导致矛盾的形式.