我国数学家证明NP=P

 
 
我国数学家证明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获得证明，对暗码学的成长是一次庞大的科学挑战。