第五百四十二章 伊夫·梅尔的小波理论 (1 / 2)
        NP=P？」也称「NP≠P还是NP=P」，被称为世界级数学难题之一。

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

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

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

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

        NP完全（NP-plete，缩写为NP-PC），是计算复杂度理论中的决定性问题之一。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有重要和积极意义」。

        内容未完，下一页继续阅读

更多完整内容阅读登陆

《墨缘文学网，https://wap.mywenxue.org》