我国数学家证明NP=P

来源：科学网

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

“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

链接阅读：

声称 P!=NP的数学家承认他的证明错了

来源：solidot（2017-9-1）

德国波恩大学数学家Norbert Blum在预印本网站发表的声称证明P!=NP的论文引发了广泛关注，全世界的数学家和计算机科学家都绞尽脑汁想搞清楚Blum是否真的证明了著名的P/NP问题。Blum的证明是基于另一名数学家Alexander Razborov发表的论文，而Razborov据称已经在Blum的证明中发现了错误，而他的证明方法也被其他数学家认为是有缺陷的。

现在，Blum更新了他的论文，承认证明存在错误，他表示将会详细解释错误，但这需要一些时间。