世界级难题
等待一个结论
8月2日，科学网发布了一篇文章，标题是《我国数学家证明NP=P》。
超模君看到这个标题时，不敢相信啊！如果是真的，姜新文教授相当于是下一个“图灵奖”得主。
NP=P?
“NP=P？”也称“NP≠P还是NP=P”,它的实质是P对NP关系问题，被称为世界级数学难题之一。
假设你参加一个盛大的宴会，想要知道里面有没有认识的人。宴会的主人对你说，你一定认识正站在甜点桌右边角落里的女士小龙女。你立刻扫向那里，发现他说的是对的。而如果他不告诉你这些，你就需要环顾整个大厅，审视过每一个人，然后才知道有没有认识的人。
宴会主人的暗示，容易找到这一步就是P，你按照他的提示发现自己认识小龙女，容易检查这一步就是NP。
这其实就是：生成问题的一个解，通常比验证一个给定的解，要花费更多时间。比如，如果让你计算世界上所有原子个数的总和，这个问题很困难，甚至无解。但是，如果有人告诉你世界上一共有500个原子，那么你能很快验证他是错的。很容易验证，却不容易求解，这种就是NP类问题。
P类问题是可以在多项式时间内解决并验证的一类问题；NP类问题是可以多项式时间验证但是不确定能否在多项式时间内解决的一类问题。
显然，所有P类问题都属于NP类问题，但是无法确定NP是否等于P。
至于引文中所提到的“多项式时间”，我们可以这样理解，多项式表达如下图：
如果要用计算机解开一个多项式，计算机是不知道这个问题难不难的，它只会拆解成非常多的步骤去执行。计算机如果觉得这个问题难，它就会花费更多的时间，时间越长就意味着问题越难，这个时间就是多项式时间。
多项式时间和非多项式时间消耗曲线对比图
也就是说，如果NP类问题无法在多项式时间内解决，那么依照当前的计算能力基本上是无解的。所以，如果NP类问题能在多项式时间内解决，也就是NP=P,它所产生的意义不可估量。
2000年初美国克雷数学研究所的科学顾问委员选定了7个数学难题，每个难题的解决有百万美元奖金，“NP=P?”正是新千年7大难题之首。
1、NP=P？
2、霍奇猜想
3、庞加莱猜想
4、黎曼猜想
5、杨—米尔斯存在性与质量间隙
6、纳维—斯托克斯存在性与光滑性
7、BSD猜想
此外，《Science》更是在2005年和2018年，将“NP=P？”列为数学科学的代表难题之一。
可怕的是，一旦“NP=P”被证明，那么基于假定“NP≠P”的学科将崩溃，比如现代密码学。而如果这个“证明”被证明是真的，举一个通俗易懂的例子：验证码将变得毫无意义。
事实上，科学网的这篇文章一出来，迎来的不是夸赞，而是怀疑。“NP=P?”这个问题是否被解决，它需要世界上的顶级数学家们进行验证，而不是凭借着某一个杂志的版面给予不确定性报道。
目前科学网的这篇文章已经被删除，但也没人证明姜教授错了。
那到底证明了吗？
有意思的是，虽然科学网的报道遭到大量怀疑，但姜新文教授的论文—《哈密顿图判定问题的多项式时间算法》，至今还没有被发现重要错误，但是也没有人站出来说他对。
其实，早在2010年，姜新文教授就已经推出了一篇长达32页的文章。这篇论文在arXiv上挂了7年，十年过去，文章删删减减，收录到知网只剩20页，最后在2020年7月发表在不是SCI的《计算机科学》杂志上。
这也是姜教授被质疑的原因之一，倘若真是具有可信性和科学性的论文，为什么至今没有得到国际学术界的认可？
另外，在这篇文章中一开始用到了12个参考文献，其中10篇都是姜新文教授自己的，不知是有意还是无意，文章中略去了其他人的名字，明显不符合学术规范。
上图为原版论文，知网新版论文有20个参考文献，6个来自于他自己
而且，他在大学从事研教三十年，可他大部分论文都发表在一本名为《计算技术与自动化》的杂志上，我们可以看一下这个杂志的影响因子。
从业至今，姜教授没有发表过一篇具有影响力的论文，突然说自己解决了一个世界级数学难题。而他的这篇论文十年间没有被任何一个有影响力的期刊接收，姜新文教授被质疑，似乎也在情理之中。
我们再来看姜教授的这篇论文—《哈密顿图判定问题的多项式时间算法》。
1859年，数学家哈密顿（Hamilton）提出了一个叫做“周游世界”的游戏。在一个正十二面体的20个顶点上，一次标注了伦敦、巴黎、莫斯科等世界上著名的大城市。要求游戏者从某个城市出发，把所有的城市都走一次，且只能走一次，然后回到出发点。
在图论中，走过途中每个顶点一次且仅一次的路线称为哈密顿路径，走过途中每个顶点一次且仅一次的回路称为哈密顿回路，具有哈密顿回路的图叫做哈密尔顿图。
根据姜教授自己的讲述：
“因为哈密顿图判定问题是NP完全问题，而任何NP完全问题有多项式时间算法，则有NP=P是普天下所有相关课本和著作的定理，所以哈密顿图判定问题有多项式时间算法等于说NP=P，如同一个人COVID-19测试阳性等于说他是新冠感染者一样。”
1、NP完全问题（NPC），Nondeterminism Polynomial complete，存在一个NP问题，所有的NP问题都可以约化它，只要解决了这个问题，那么NP问题就解决了。需要满足2个条件：它首先是一个NP问题；所有的NP问题都可以约化到它。
2、NP难问题，NP-hard，它满足NPC问题定义的第二条但不一定满足第一条，即所有的NP问题都能约化到它，但是不一定是一个NP问题。
它们四个的关系可以用下图表示：
即判定哈密顿图是一个NPC问题，找到了任何一个NPC问题的多项式算法，就能够得出P=NP的结论。
换句大白话就是：条条大路通罗马，找到任何一条能通往罗马的路，那么就可以说NP=P。
姜教授认为他这样证明是没有问题的，十年来，也一直在等人给他一个结论。
激烈的讨论
“NP=P？”的分量非常重，这么多年没有得出一个结果，不是因为没有人研究，而是真的好难。
2010年8月6日，惠普实验室的vinay deolalikar教授宣布证明了P≠NP，证明论文多达100页。
vinay deolalikar教授邮件内容
deolalikar教授把他的证明过程放在自己的博客主页上，8月8日，计算机科学家Lipton在博客上讨论了这篇论文，评价道：
“这是一个值得认真对待的证明”。
事情发生后，引来了大量学术性的评论，很多都是同行，看法各有不同。
8月9号，Lipton在参考了大家的评论后，又重新写了一篇新的评论，指出了deolalikar论文中的一些漏洞。
因为在这篇文章下面有大量有价值的评论，犹他大学计算机学院教授Venkatasubramanian建立了一个可以被用户编辑的谷歌文档，这些评论都被整理在其中。
8月10号，在陶哲轩的帮助下，这个文档被转换成一个WIKI架构的页面。
Lipton的文章下面成了大家的讨论平台，许多学术性的批评出现，有更多的科学家参与到博客的讨论和WIKI页面的编辑。deolalikar教授也在各方质疑下不断更新自己的论文。
这场讨论推进了deolalikar教授改进自己的证明，也促进了公众对NP=P?问题的了解。Lipton和陶哲轩认为这场在互联网平台上的讨论产生了良好效果。
8 月 12 日，Lipton公布出了一封来自美国理论计算机科学家尼尔.伊莫曼（ Neil Immerman ）的信，指出了两个此前未被认真讨论的漏洞。
8 月 13 日，Deolalikar 贴出了一篇关于自己的证明的解释性文档。
8 月 14 日，在很多科学家的共同讨论中，人们逐渐厘清 Deolalikar 的论文的根本问题在于把两个没有在论文中被严格定义出来的直观概念混淆在一起，从而做出了不完善的论证。
8 月 15 日，Lipton 贴出了他对于一周以来讨论的总结。
人们关于论文已经基本上认为证明不能成立，当然也可能多数人都犯了错，关于“NP=P?”问题的讨论至今仍在继续。
相较于vinay deolalikar教授长达100页的论文，姜教授的论文实在是太短了。
另外，在姜教授的这篇论文中，我们可以看到，他的结束语是“结果可能对于证明NP=P有重要意义”，和他5年前在自己博客中的说辞已经发生了变化。
上图来自新版论文截图
上图为2015年姜教授的博客内容截图
“NP=P？”问题的重要性不言而喻，就连陶哲轩大神也对它十分关注。这也就是为什么消息一出来，国内各大新闻网站就把它推上了首页，引起了大家的广泛质疑，因为所有人都想见证这历史性的一刻。
而即使这次“NP=P”被证明是错的，也都将会是中国数学史上一次伟大而又不可磨灭的大事件。
参考文献：
姜新文.哈密顿图判定问题的多项式时间算法[J].计算机科学,2020,47(07):8-20.
作者简介：超模君，数学教育与生活自媒体博主，新晋理工科奶爸。出版过《芥子须弥 · 大科学家的小故事》；《数学之旅·闪耀人类的54个数学家》。后续数学文化创意多多，欢迎关注认识！
热门跟贴