#千禧难题##P/NP问题#
从历史的开端，人类就一直在解决各种问题，从早期农业到太空探索，解决数学问题似乎是人类生存的一个关键因素。
自上世纪70年代以来，一些曾经单调乏味的计算问题在一瞬间就可以解决，这主要是由于计算机计算能力的指数级增长。然而，一些独特的问题仅仅通过技术进步是无法解决的，即使对于最强大的计算机来说，解决这些问题所花费的时间比人的一生还要长。这些问题似乎都有一个共同点，即P/NP问题。
1859年，英国数学家威廉·哈密顿提出了“周游世界游戏”：用一个正12面体的20个顶点来表示地球上的20个城市，如何才能从某个城市出发，沿着各条棱走正好只经过每个城市一次，最后返回到出发地点？这条路径称为哈密顿循环，而这个简单的博弈产生了图论中的一个重要问题，即哈密顿循环决策问题——给定一个任意地图，如何知道它是否包含一个哈密顿循环。
解决这个问题的一种方法是遍历图中任何可能的路径，并检查该路径是否为哈密顿循环。然而，由于可能路径的数量可以达到n的阶乘，即使一个只有40个顶点的图也可能包含超过10^45条路径，使得问题几乎不可能在合理的时间内解决(即使对于最强大的处理器也是如此)。此外，由于顶点数量与路径数量之间的阶乘依赖关系，即使仅增加一个顶点，也需要大幅提升计算机的计算能力。可以说，增长的根本性质使这个问题比其他问题更困难。
为了使这个问题形式化，计算机科学家使用了时间复杂度的尺度。时间复杂度是指解决一个问题需要的步长及所需步长如何随问题大小而变化。给定一个算法，算法的时间复杂度被描述为一个渐近函数，它依赖于算法的输入大小。主要有阶乘，指数和多项式复杂度函数。
多项式增长被认为比其他增长更为缓慢，因为增大输入不会导致所需步骤急剧增加。选择多项式来表示有效的计算具有一定的合理性。一个较明显的区别是，多项式在加法、乘法和组合下的闭包保留了自然编程实践中的效率概念，比如将程序链接到一个序列中，或者将一个程序嵌套到另一个程序中。
多年来，为了有效地解决哈密顿循环决策问题，科学家们进行了许多尝试。其中一种是Held-Karp算法，它能在指数时间内解决这个问题。然而，没有已知的算法可以在多项式时间内解决这个问题，因此，它仍然被认为是一个难题。
然而，一个有趣的现象发生了，尽管不能有效地解决这个问题，但在给定一个路径图中，至少可以有效地检查是否是哈密顿循环，因为简单循环中的最大顶点数为n，则遍历路径所需的时间被多项式限定为n。似乎许多其他决策问题都具有这一特性——不管它们是否能被有效地解决，它们所提出的解决方案都能被有效地验证。这类问题被定义为NP。
进一步思考问题的可解性与其解的可验证性之间的关系，可以得出结论：如果一个决策问题是有效可解，那么它的解必须是有效可验证的。因为如果一个决策问题是可以有效地解决的，那就意味着可以有效地找到它的解决方案。然后，给出一个解决方案，可以简单地通过与问题的实际解决方案比较来验证它。换句话说，生成解决方案的算法的正确性自动证明了该解决方案。从这个结论可以看出，很明显，NP包含的问题子集也是有效可解的。这个子集被定义为P。
P是所有可有效解决的决策问题的集合，是NP的一个子集，其基本算法是多项式时间可解的。
哈密顿循环决策问题有一个有效的算法可以验证它的解，因此属于NP。有人可能会问，这个问题是否在P中，一方面，我们不知道是否有一个有效的算法可以解决这个问题；另一方面，没有证据表明这样的算法不存在。事实上，对于许多其他主要问题，如布尔可满足性问题、旅行商问题、图着色问题等，尽管已经证明这些问题是NP，但没有证据表明它们属于P 。这就是P=NP问题的意义所在：P和NP真的是一样的吗？如果是，这就意味着NP中的所有问题都可以被有效地解决，尽管我们仍然没有找到实现这一点的神秘算法。否则，在NP中存在一些无法有效解决的问题，任何尝试解决将意味着浪费我们的时间和精力。
在数学、优化、人工智能、生物学、物理学、经济学和工业领域中，存在着数以千计的NP问题，这些问题都是出于不同的需要而自然产生的，其有效的解决方案将使我们在许多方面受益。证明P=NP将意味着所有这些难题都可以在多项式时间内解决，这将导致在那些卓越的算法之后进行大规模的智力追求。一旦发现，这些算法将有可能推动人类的进步。
从历史的开端，人类就一直在解决各种问题，从早期农业到太空探索，解决数学问题似乎是人类生存的一个关键因素。
自上世纪70年代以来，一些曾经单调乏味的计算问题在一瞬间就可以解决，这主要是由于计算机计算能力的指数级增长。然而，一些独特的问题仅仅通过技术进步是无法解决的，即使对于最强大的计算机来说，解决这些问题所花费的时间比人的一生还要长。这些问题似乎都有一个共同点，即P/NP问题。
1859年，英国数学家威廉·哈密顿提出了“周游世界游戏”：用一个正12面体的20个顶点来表示地球上的20个城市，如何才能从某个城市出发，沿着各条棱走正好只经过每个城市一次，最后返回到出发地点？这条路径称为哈密顿循环，而这个简单的博弈产生了图论中的一个重要问题，即哈密顿循环决策问题——给定一个任意地图，如何知道它是否包含一个哈密顿循环。
解决这个问题的一种方法是遍历图中任何可能的路径，并检查该路径是否为哈密顿循环。然而，由于可能路径的数量可以达到n的阶乘，即使一个只有40个顶点的图也可能包含超过10^45条路径，使得问题几乎不可能在合理的时间内解决(即使对于最强大的处理器也是如此)。此外，由于顶点数量与路径数量之间的阶乘依赖关系，即使仅增加一个顶点，也需要大幅提升计算机的计算能力。可以说，增长的根本性质使这个问题比其他问题更困难。
为了使这个问题形式化，计算机科学家使用了时间复杂度的尺度。时间复杂度是指解决一个问题需要的步长及所需步长如何随问题大小而变化。给定一个算法，算法的时间复杂度被描述为一个渐近函数，它依赖于算法的输入大小。主要有阶乘，指数和多项式复杂度函数。
多项式增长被认为比其他增长更为缓慢，因为增大输入不会导致所需步骤急剧增加。选择多项式来表示有效的计算具有一定的合理性。一个较明显的区别是，多项式在加法、乘法和组合下的闭包保留了自然编程实践中的效率概念，比如将程序链接到一个序列中，或者将一个程序嵌套到另一个程序中。
多年来，为了有效地解决哈密顿循环决策问题，科学家们进行了许多尝试。其中一种是Held-Karp算法，它能在指数时间内解决这个问题。然而，没有已知的算法可以在多项式时间内解决这个问题，因此，它仍然被认为是一个难题。
然而，一个有趣的现象发生了，尽管不能有效地解决这个问题，但在给定一个路径图中，至少可以有效地检查是否是哈密顿循环，因为简单循环中的最大顶点数为n，则遍历路径所需的时间被多项式限定为n。似乎许多其他决策问题都具有这一特性——不管它们是否能被有效地解决，它们所提出的解决方案都能被有效地验证。这类问题被定义为NP。
进一步思考问题的可解性与其解的可验证性之间的关系，可以得出结论：如果一个决策问题是有效可解，那么它的解必须是有效可验证的。因为如果一个决策问题是可以有效地解决的，那就意味着可以有效地找到它的解决方案。然后，给出一个解决方案，可以简单地通过与问题的实际解决方案比较来验证它。换句话说，生成解决方案的算法的正确性自动证明了该解决方案。从这个结论可以看出，很明显，NP包含的问题子集也是有效可解的。这个子集被定义为P。
P是所有可有效解决的决策问题的集合，是NP的一个子集，其基本算法是多项式时间可解的。
哈密顿循环决策问题有一个有效的算法可以验证它的解，因此属于NP。有人可能会问，这个问题是否在P中，一方面，我们不知道是否有一个有效的算法可以解决这个问题；另一方面，没有证据表明这样的算法不存在。事实上，对于许多其他主要问题，如布尔可满足性问题、旅行商问题、图着色问题等，尽管已经证明这些问题是NP，但没有证据表明它们属于P 。这就是P=NP问题的意义所在：P和NP真的是一样的吗？如果是，这就意味着NP中的所有问题都可以被有效地解决，尽管我们仍然没有找到实现这一点的神秘算法。否则，在NP中存在一些无法有效解决的问题，任何尝试解决将意味着浪费我们的时间和精力。
在数学、优化、人工智能、生物学、物理学、经济学和工业领域中，存在着数以千计的NP问题，这些问题都是出于不同的需要而自然产生的，其有效的解决方案将使我们在许多方面受益。证明P=NP将意味着所有这些难题都可以在多项式时间内解决，这将导致在那些卓越的算法之后进行大规模的智力追求。一旦发现，这些算法将有可能推动人类的进步。
#求是网评#【以全球视野谋划和推动科技创新】党的十九大以来，我国秉持人类命运共同体理念，扩大科技领域开放合作，深入参与全球科技创新治理，形成了全方位多层次广领域的科技开放合作新格局，科技创新的全球化水平和国际影响力日益提升，为参与解决人类面临的重大挑战、推动科技创新成果惠及更多国家和人民作出了突出贡献。https://t.cn/A6XSd3fW
#求是网评#【以全球视野谋划和推动科技创新】党的十九大以来，我国秉持人类命运共同体理念，扩大科技领域开放合作，深入参与全球科技创新治理，形成了全方位多层次广领域的科技开放合作新格局，科技创新的全球化水平和国际影响力日益提升，为参与解决人类面临的重大挑战、推动科技创新成果惠及更多国家和人民作出了突出贡献。https://t.cn/A6XSd3fW
✋热门推荐