千禧年7大数学难题之一被中国人破解？国防科大教授发文证明NP=P

【新智元导读】近日，「计算机科学」刊发了一篇题为《哈密顿图判定问题的多项式时间算法》，该文宣称可以间接证明数学和计算机科学领域的NP=P难题。

论文刊发后，短短数天时间下载量就破千，但是关于这一证明的有效性，引发了

网友的热议。

• NP=P？为什么这么难

「NP=P？」也称「NP≠P还是NP=P」，被称为世界级数学难题之一。

2000年5月，美国克雷数学研究所（CMI）在巴黎举行的千年数学大会上宣布对攻克世界7个数学难题的悬赏，每个问题100万美元奖金，「NP=P？」问题被列为7大难题之首。

7大难题中，目前只有「庞加莱猜想」被俄罗斯数学家佩雷尔曼证明（2002年），其他难题均悬而未决。

如果一个问题能在多项式时间内找到答案，我们称之为「类P 」或「P」问题。

对另一类问题，没有已知的方法可以快速找到答案，但如果提供提供一个正确的答案，就能快速验证，这类可以在多项式时间内验证但是不确定能否在多项式时间内解决的称为「NP」问题。

NP完全（NP-Complete，缩写为NP-C或NPC），是计算复杂度理论中的决定性问题之一。NP完全是NP与NP困难的交集，是NP中最难的决定性问题。因此NP完全问题应该是最不可能被化简为P（多项式时间可决定）的决定性问题的集合。若任何NPC问题得到多项式时间的解法，那此解法就可应用在所有NP问题上。

「NP=P？」问题可以简单理解为：如果问题的正面答案可以很快验证，其答案是否也可以很快计算？

「NP=P？」的答案将决定在多项式时间内验证的问题是否也能在多项式时间内解决。如果是P≠NP，那就意味着NP中存在比验证更难的问题：它们不能在多项式时间内解决，但答案可以在多项式时间内验证。

「NP=P？」的问题具有十分重要的意义，现代密码学建立在NP≠P的假定之上，如果NP=P，从理论上说，密码学会彻底崩溃。

• 哈密顿图判定问题是NP完全的吗？

根据姜教授自己的陈述，「因为哈密顿图判定问题是NP完全问题，而任何NP完全问题有多项式时间算法则有NP=P是普天下所有相关课本和著作的定理，所以哈密顿图判定问题有多项式时间算法等于说NP=P，如同一个人COVID-19测试阳性等于说他是新冠感染者一样」。

哈密顿图是一个无向图，要求由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（含有图中所有顶点的路径称作哈密顿路径）。

十二面体中的哈密顿回路

寻找哈密顿路径是一个典型的NP-完全问题，所以大多认为通过哈密顿图判定可以间接证明NP=P的问题。

为了减少刺激性，姜新文教授将摘要中「暗含NP=P」几个字替换成「对证明NP=P有重要和积极意义」。

• 网友热议：论文的可行性存疑，如果是真的将击溃现有加密体系

论文发表后，引发了很多网友讨论。

论文太短了，不可能证明这种难度的问题。

此前，曾有网友做了一些工作，认为这篇论文是偏「民科」的。他认为，姜新文教授此前没有发表过任何权威的论文，而且这篇论文的长度太短了，对于这种难度的问题来说是完全不够的。

当然这位网友也不是凭空猜测，他给出了自己的反例证明，感兴趣的读者可以参考文末原文链接。

另外，这篇论文的一个重要前提「MSP问题是一个NPC问题」，但是这个结论也不一定是对的。

亲历者：退休老教师只是想找个答案

曾亲自上过姜老师课的网友表示，姜老师具备发表这篇论文的基本科学素养，计算复杂度知识和严谨逻辑推理能力。如果结论是错的，希望有人能告诉他错在哪，对于一个退休的老人，他只是求个答案。

至于论文中的maybe等词，个人理解一是研究者的谦虚，二是确实也不能100%的保证证明没问题。

如果NP=P问题得到解决，世界将会怎样？

虽然没有网友说的这么夸张，但是NP=P如果得到证明，产生的影响还真挺大的。

到那时，我们常用的MD5加密算法将会失效，判定一个串的MD5是否为给定值与寻找一个MD5等于给定值的串一样轻松，RSA算法也不再有效，寻找一个质因子和判断整除性也变得一样简单。

事实上，基于类似原理的任何加密算法都将成为一纸空谈，计算机可以轻松根据密文推算出解密算法（只要这个算法是多项式的），互联网将没有任何安全性可言。

参考链接：

https://www.zhihu.com/question/29240825/answer/43662453

https://www.zhihu.com/question/411543712

http://www.matrix67.com/blog/archives/2552

http://blog.sina.com.cn/s/blog_54de27b80102yz41.html