计算机证明数学定理：科学网发布文章称

计算机证明数学定理：科学网发布文章称姜新文从1986年开始讲授《算法设计与分析》课程，结合此前学习图论时关于哈密顿图判定问题的思考，开始研究P对NP关系问题。9年之后，姜新文于1995年发表了研究成果《简单无向图H性质判定》，开始思考运用整体观思路来处理一个有限系统的计算问题。据介绍，20世纪，现代计算机问世，NP与P的关系问题就成为计算机科学和数学交叉领域的基础科学问题。通常，算法求解一个问题需要耗费时间，这被称为算法的时间复杂度。求解同一个问题的不同算法耗费的时间可能不同，只有采用多项式时间算法才能最有效解决问题。NP≠P，其核心是否定不同选择方法，认为有些问题不存在多项式算法。而姜新文证明了“NP=P”，表明多项式算法实际上是存在的。- 知乎https://www.zhihu.com/question/411543712“NP=P？”也称"NP≠P还是NP=P”，实质是P对NP关系问题，被称为世界级数学难题之一

2020年7月出版的《计算机科学》（中国计算机学会会刊）发表了国防科技大学教授、湘潭大学计算机学院特聘教授姜新文题为《哈密顿图判定问题的多项式时间算法》的论文，这标志着在数学和计算机科学领域中最为重要的难题之一 “NP=P？”得到科学证明，论文刊出几天后下载量近千次，引发有关学术群体热议。

>>>>

本文仅作为学术分享，如有侵权，删文处理

如何看待科学网发布文章称「我国数学家证明 NP=P」，是真的吗？如果是，会带来怎样的影响?

- 知乎https://www.zhihu.com/question/411543712

“NP=P？”也称"NP≠P还是NP=P”，实质是P对NP关系问题，被称为世界级数学难题之一。2000年5月，美国克雷数学研究所（CMI）在巴黎举行的千年数学大会上宣布对攻克世界7个数学难题的悬赏。P对NP关系问题被列为新千年7大难题之首。

2005年《科学》杂志将"NP=P？”问题作为数学科学的代表，列为25个学科难题之一。2018年《科学》杂志再次列出125个亟待解决的科学难题，其中第19个问题就包含"NP=P？”问题。迄今为止，新千年7大数学难题中除了俄罗斯数学家佩雷尔曼2002年证明了有关拓扑学的“庞加莱猜想”之外，其他难题均悬而未决。

据介绍，20世纪，现代计算机问世，NP与P的关系问题就成为计算机科学和数学交叉领域的基础科学问题。通常，算法求解一个问题需要耗费时间，这被称为算法的时间复杂度。求解同一个问题的不同算法耗费的时间可能不同，只有采用多项式时间算法才能最有效解决问题。NP≠P，其核心是否定不同选择方法，认为有些问题不存在多项式算法。而姜新文证明了“NP=P”，表明多项式算法实际上是存在的。

姜新文从1986年开始讲授《算法设计与分析》课程，结合此前学习图论时关于哈密顿图判定问题的思考，开始研究P对NP关系问题。9年之后，姜新文于1995年发表了研究成果《简单无向图H性质判定》，开始思考运用整体观思路来处理一个有限系统的计算问题。

他首先建立了一套基于数学归纳法的证明框架，然后坚持探索满足这套证明框架的算法设计。从1995年开始之后的15年中，经历了2000次以上设计、修改与调整，到2010年底得到预期效果。姜新文35年的潜心探索，终于获得成功！

“NP=P”得到证明具有重要的科学意义与应用价值。因为这将为计算机科学领域带来截然不同的理论极限和发展前景。在现代经济社会中，大量科研、生产、国防与社会服务过程都需要采用正确的快速计算方法。可以期待，在“NP=P时代”，地球科学、生命科学、宇宙科学、环境科学、生物科技、材料工程、管理科学、数学科学、物理科学等多个学科的研究都将得到更深入的推进。

此外，由于现代密码学是建立在NP≠P的假定之上，而现在NP=P得到证明，对密码学的发展是一次巨大的科学挑战。

相关论文信息：doi: 10.11896/jsjkx.191200176

本公众号回复：NP，即可获取论文全文

作者@ 留德华叫兽的回答

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

NP完全问题(NP-C问题)

即NP是否等于NP

是世界七大数学难题之一

作为运筹学|组合优化的博士 ，硕士对这个问题证明的某种特殊情况做出过一丁点微小的贡献（待我娓娓道来：）。博士研究组合优化问题（NP难）的整数规划建模和精确算法 并且在德国博士答辩的口试题之一就是关于NP问题的 ，觉得有必要用最通俗的语言先为大家科普一下

1. 什么叫P 和 NP问题

首先这是一个算法复杂度的概念 P问题：多项式时间“可解”的"简单"问题 NP问题：给一个解，多项式时间可以判定该解是否“正确” NP完全问题：可以被所有NP问题多项式时间“转化”到的"最难"的一类问题 （目前比较“通用”的有21个该问题）

以上打引号地数学上不是很精确，目的是让大家更好地get point，下图很好地刻画了P和NP的关系

2. NP难有多难

大家应该都听说过指数爆炸吧？ 虽然还未能证明P是否等于NP，但是学术界“普遍”认为它们不等。因此 ，求解一个一般的NP难问题的精确解（全局最优解），它的算法复杂度通常是指数级的 。

什么意思呢？ 算法复杂度是浮点运算数相对于变量n的一个关系。假设该指数的底是2 即：算法复杂度是O(2^n) ，也就是说 ，如果当变量n=100的时候 ，运算时间是10秒钟，那么当变量n=101的时候，运算时间“最坏情况”是20秒钟(直接翻倍) 。当n=102 ，运算时间最坏 40秒(四倍) 。当n=110，运算时间最坏是 10240秒=2.844小时！！！ (多了10个变量，运算时间是2的10次方倍)

3. 退而求其次-近似算法、启发式算法

既然要求得全局最优解是指数级算法复杂度的 ，工业界可没有这个耐心等这么久 ，（例如：网约车的实时派单、导航软件计算最短的k条路线），于是有了近似算法和启发式算法 。

近似算法是指虽然我求不到全局最优解， 但是我设计一种算法，用数学证明该算法得到的解在全局最优解的1/k-k倍以内 。并且该算法通常是多项式的--快。

启发式算法（如：贪婪算法），设计一种快速的多项式时间算法，求得一个正确的解 但是不知道这个解的质量（离全局最优解有多远）

具体请见：https://zhuanlan.zhihu.com/p/30140008

4. 回到正题：如何证明NP=P及硕士期间做过的微小工作

只要证明21个NPC问题中的任何一个

是多项式时间可解的， 即证明了NP=P，例如经典的背包问题（Knapsack problem）

定义： 我们有 n 种物品，物品 j 的重量为wj，价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。

https://zh.wikipedia.org/wiki/背包问题

我在美国Clemson读研期间的硕士论文，证明了一种特殊的背包问题是多项式时间可解的 ，有多特殊呢？

上式中目标函数的系数p必须满足 ：

可以简单地理解为：系数p呈指数级上升

当系数满足这个条件的时候，我们证明了这个整数规划的系数矩阵是Total Unimodular的 ，即这个整数规划问题等价于它的线性规划松弛，因此这类背包问题是多项式时间可解的 。这大概是我这个数学博士在学术上最高光的时刻， 从此一路走下坡，越做越应用 ，甚至转行到了令数学同行所不齿的人工智能。

书归正传 文章最后发表在了JOGO上面 感兴趣的小伙伴可以下载预印版

http://www.optimization-online.org/DB_FILE/2015/12/5246.pdf www.optimization-online.org

从这个意义上讲 我是不是也对证明P等于NP？做出了一丁点微小的贡献呢？ 笑～逃～

5. 假设P=NP

世界会怎样？世界将一片美好 。卡普的21个NP完全问题将是多项式时间可解的

工业界诸多实际的组合优化问题将会变得简单 ，任何密码将会在“短时间”内被攻破。整数规划、01规划、背包问题全部获解，运筹学将登上一个全新的高度；数据库的串行化、多处理器调度等问题也随之解决，大大提高了计算机的性能。详见：

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

以及， 我们这些研究大规模组合优化、离散优化精确解的小伙伴都要失业了？ 因为它们变成了很“简单”的问题了 还用得着我们去研究么 哈哈

简单点评:

在被国际最权威的数学|理论计算机杂志 同行评审、刊登出来之前 这个千禧年大奖难题哪有这么容易攻破 ( @Yuhang Liu 提到:国际审稿都给了拒稿) 更何况发表这篇文章的 是一本既不是SCI也非EI的中文“学术”杂志。因此也就没有花时间去“找茬”，但我还是很钦佩老教授退休了还继续啃硬骨头的钻研精神，也很佩服《计算机科学》这本杂志。不管怎么说，都是一次历时七年以上、有意义的尝试，而非我这种知乎答题者花了3小时写的“民科”。

我这篇科普文，有不专业的地方， 还请专业人士指正 。

最后，在查看其他回答的时候 ，发现 @G.Cui 的回答更完整地科普了什么叫P和NP。

作者@ G.Cui的回答

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

更新：科学网的原文似乎已撤下。

实际上对相关内容一点也不了解的人很可能会低估这个问题的难度，有的答主不具体指出错误会让一些旁观者感到不满，这也可以理解，但是其他答主也不能走向另一个极端，更有甚者用民族主义绑架数学、科学，我认为嘲讽攻击何时也不应该有。

简单来说，论文证明的方向——“证明一个NPC问题是P的”是对的，也就是说，如果论文的所有细节正确，则 P=NP 。论文本身的正确性尚未讨论出公认结果，媒体给的报道如果认为是“假定论文正确，则P=NP ”则基本正确，无条件嘲讽没有必要，但是报道中还是有些科普细节不当。

我并没有水平评价论文内算法的正确性，我只是想对报道中其他的错误进行评论。因为问题是“如何看待科学网的文章”，我想我对报道的评论并不属于无关内容，请轻喷。

对论文本身的评价参见高赞，下面我只对科学网的报道中的问题说几句——

报道里：

NP≠P，其核心是否定不同选择方法，认为有些问题不存在多项式算法。而姜新文证明了“NP=P”，表明多项式算法实际上是存在的。

这根本就没理解P v.s. NP 问题是啥意思，

1.“有些问题不存在多项式算法”，等价的说法应该是“存在一些 问题 不是 P 问题”，也就是说，不是所有问题都是 P 的；

2.P≠NP 等价的说法应该是“存在一些NP问题不是P问题”。

前者与 P v.s. NP 毫无关系，因为早就知道有的问题不存在多项式算法（比如 HALT 都不是可判定的），报道把这二者混为一谈，绝口不提 NP 问题是什么，这是不对的。

姜的文章就是试图做最后一条，他论文的方向在说某个问题是NPC的，然后给了一个多项式算法，所以证明 P=NP。证明大方向没错，但这些步骤的细节估计（我没能力给出确定的回答，但我的直觉是 P≠NP）是有问题的。

参考

1.^Wikipedia. P. https://zh.wikipedia.org/wiki/P_(複雜度)

2.^Wikipedia. NP. https://zh.wikipedia.org/wiki/NP_(複雜度)

3.^Wikipedia. NPC. https://zh.wikipedia.org/wiki/NP完全

4.^https://zh.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg

作者@ Climber.pI 的回答

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

Gerhard J Woeginger 在去 RWTH Aachen 之前 曾经维护了一个关于 P 和 NP 关系的各种伪证的页面 (一直更新到了 2016 年):

P-versus-NP page www.win.tue.nl

通过简单的搜索不难发现第 53 条如下: 53. [Equal]:In April 2009 Xinwen Jiang published a proof for P is equal to NP. He provided an algorithm for the Hamilton circuit problem and states"It seems our algorithm is a polynomial one".The paper can be found athttp://xinwenjiang.googlepages.com/. An earlier version of his paper was published in a Chinese journal in 2007. Further versions have been published in 2010 and 2011. More information on the current version of the proof is available athttp://trytoprovenpvsp.blog.sohu.com/entry/. Since May 2013 the paper"A Polynomial Time Algorithm for the Hamilton Circuit Problem"is available athttp://arxiv.org/abs/1305.5976. (Thanks to Maris Ozols for providing some of these links.)

有兴趣查证各种链接的同学 可以结合 https://archive.org/web/ 来考证相关的历史链接.

我也不是很理解为什么要讨论这种 not even wrong 的东西. 但是很迷的是 看楼下的博客链接 这一系列结果竟然还拿到了 NSFC 的资助? 比起直接证明 P 和 NP 的关系 建议考虑证明或推翻以下较为容易的问题:

● 证明 P 不等于 PSPACE;

● 给出 Learning with Error 问题的经典或量子多项式时间算法;

● 证明 AM=MA 如果觉得太容易的话 可以考虑证明 P=BPP;

● 证明 QCMA = QMA 或 QCMA = QMA(2) 或者里面随便挑两个证明相等;

● 证明 NL=L 或 BPL=L;

● 证明 BQP=QPIP.

哦忘记说了 第二项是 P=NP 的推论. 因为 LWE 的 hardness 证明依赖的 poly-approximated GapSVP 是在 NP cap coNP 里的 所以能导出 LWE 的经典多项式时间算法. 作为脚注 Regev 曾在某次报告中表示 “每年都有几天 我早上醒来 会收到邮件声称给出了某些 lattice problems 的多项式时间的算法”. 如果有人能给出 LWE 的 (量子) 多项式时间算法的话 我会非常高兴 因为我个人很不喜欢现在 LWE-based quantum delegation 的这些结果.

最容易证明的可能是第五项 今年 STOC 的 workshop 上有几个大佬表示基于近年的一系列进展 有望在十年内证明 BPL=L -- 目前最好的上界是二十多年前 Saks-Zhou 的 BPL is in L^{3/2}. 剩下最容易的可能是第三项 但是现在甚至没有比 P=BPP 更弱的备选前提条件. 第四项和第六项目前没有任何头绪 第六项也有一些人认为不成立.

作者@ Manchery 的回答

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

不认可在该问题下用媒体夸大其词这一人民群众喜闻乐见的现象而掩饰了问题本质的一切回答，包括最高赞。

首先给出我认知中的一个事实：

判定哈密顿图是一个 NPC 问题；找到了任何一个 NPC 问题的多项式算法，就能够得出 P=NP 的结论（从这一结果得到 P=NP 的这一过程非常简单，就像证明了三边相等，则两个三角形相似一样简单，因此足以略过不提）。

按照上面的事实，“如果这位老师的证明是正确的，那么他确实就是证明了 P=NP”。这一说法是没有问题的，包括这位老师自己也就是这么认为的，比如他自己写到：

《哈密顿图判定问题的多项式时间算法》发表_XinwenJiang_新浪博客：

https://link.zhihu.com/?target=http://blog.sina.com.cn/s/blog_54de27b80102yz41.html

《哈密顿图判定问题的多项式时间算法》发表在2020年第7期的《计算机科学》。因为哈密顿图判定问题是NP完全问题，而任何NP完全问题有多项式时间算法则有NP=P是普天下所有相关课本和著作的定理，所以哈密顿图判定问题有多项式时间算法等于说NP=P，如同一个人COVID-19测试阳性等于说他是新冠感染者一样。虽然最终按照建议和希望，将摘要中“暗含NP=P”几个字替换成“对证明NP=P有重要和积极意义”，以减少刺激性，但这句话本来可以整体不说。陈景润发表在《科学通报》的、关于求证哥德巴赫猜想的巅峰之作，也只是命名《表达偶数为一个素数及一个不超过两个素数的乘积之和》。感谢所有相关的人的辛勤工作。2020年发生的世界性疫情没有阻挡我们的科学攀登。这一次，扎扎实实做研究，把论文写在中国大地上的要求，给了所有的人奋勇前进的无穷力量。当人们传颂国外数学家因为疫情宅在家里解决数学难题的时候，同样宅在家里的他们的中国同行，也同样在做着艰苦的努力。

以及他的挂在arxiv上的论文的摘要也写到：

Our result implies NP=P

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

因此，只能说媒体并不具备鉴别这一论文真伪的能力（这是十分常见的），但我们并不能说媒体夸大其词了。我更相信媒体听到的就是“我们证明了P=NP”（仅是我个人相信）。

我认为对这个问题的关注点更应该放在这个证明对不对，如果不对，他为什么发表了，如果对，为什么没有得到国际学术界的认可。更应该把这一问题类比成 望月新一在日本宣布了自己证明了ABC猜想但遭受了质疑，而不是类比为一次媒体夸张报导的事故（当然媒体未经严谨求证的报导也是一个问题，但这不同于夸张报导）。

关于这一证明对不对，也有很好的回答，以及该回答最下面也有 关于P、NP等的背景知识 可供参考：

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

另一个解释了 P 和 NP 是什么的回答（他意在指出即使这篇报导的主要内容在证明正确这一前提下是没有问题的，但其中对于背景知识的科普依然是有瑕疵的）

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

另一高赞回答提到了这位老师的这一证明已经被人收录在错误证明里面了（但我并没有能力辨别这一证明的真伪，我在这里也并不是为了强调他是错的或对的）

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

来源：运筹OR帷幄