第六百六十一章 哈密顿图判定问题的多项式时间算法（1 / 2）

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

2000年5月，美国克雷数学研究所（cplete，缩写为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有重要和积极意义」。