研究员证明了P!= NP

kee020041

哇！我真的好久没有上“逻辑数学”了。大家好。

惠普研究实验室的研究员Vinay Deolalikar声称证明了P!= NP。
P/NP问题涉及的是复杂度类P与NP的关系，P事实上是NP的一个子集，NP是指非确定性图灵机在多项式时间内计算的问题，而P是指确定型图灵机在多项式时间内解决的问题。P是否等于NP是克雷数学研究所的千禧年大奖难题之一。Deolalikar的论文长达100页，目前尚未经过同行审议，因此任何人都可以在论文中寻找漏洞或错误。如果Deolalikar的证明是正确的，那么他将有资格获得克雷提供的百万美元奖金。

哪位大大有空去读哪100页的论文啊？

Link - 更多消息

100页的论文

一起来讨论讨论。

数学系

http://cforum1.cari.com.my/viewt ... &extra=page%3D1

数学系

http://cforum1.cari.com.my/viewt ... &extra=page%3D1