从历史的开端，人类就一直在是解决各种问题。从早期农业到太空探索，解决数学问题似乎是人类生存的一个关键因素。自上世纪70年代以来，一些曾经单调乏味的计算问题在一瞬间就可以解决，这主要是由于计算能力的指数级增长。然而，一些独特的问题仅仅通过技术进步是无法解决的，即使对于最强大的计算机来说，解决这些问题所花费的时间比人的一生还要长。事实上，现代加密技术依赖于这样一个事实：大质数不可能因式分解。这些问题似乎都有一个共同的难题，也就是P（ polynomial time）对NP（ non-deterministic polynomial time）谜题的核心——什么是可化简的，什么是不可化简的？

1859年，爱尔兰数学家威廉·汉密尔顿画了一个叫做伊科希的数学游戏。这个游戏是在一个由20个角（顶点）组成的木制十二面体表面上进行的。每个角落都标上了一个城市的名字。游戏的目标是找到一个循环，即访问每个顶点一次，然后返回起点。这种路径称为哈密顿循环。这个简单的博弈产生了图论中的一个重要问题，即哈密顿循环决策问题——给定一个任意地图，我们如何知道它是否包含一个哈密顿循环？

• 二维平面图形的十二面体。一个可能的哈密顿循环用红色表示。

解决这个问题的一种方法是遍历图中任何可能的路径，并检查该路径是否为哈密顿循环。然而，由于可能路径的数量可以达到n的阶乘。这样，即使一个只有40个顶点的图也可能包含超过10^45条路径，使得问题几乎不可能在合理的时间内解决(即使对于最强大的处理器也是如此)。此外，由于顶点数量与路径数量之间的阶乘依赖关系，即使我们再增加一个顶点，也需要大幅提升计算机的计算能力。我们可以说，阶乘增长的根本性质使这个问题比其他问题更困难。这就是数学问题的艰巨性——如果一个问题需要的资源随着投入的增加而急剧增加，那么这个问题就非常棘手。

为了使这个想法形式化，计算机科学家使用了时间复杂度的尺度。时间复杂度指的是解决一个问题需要多少步长，以及所需的步长如何随问题的大小而变化。给定一个算法，算法的时间复杂度被描述为一个渐近函数，它依赖于算法的输入大小。

• 一个算法的时间复杂度被描述为一个渐近函数，它依赖于算法的输入大小。一个主要的区别是阶乘，指数和多项式复杂度函数。

对于具有多项式复杂度的算法和具有更基本复杂度函数的算法，有一个基本的区别。这种区别主要是由于多项式增长被认为比其他增长更为缓慢，因为增大输入不会导致所需步骤急剧增加。多项式（Polynom）是一种只涉及加、减、乘和非负整数指数运算的构造，因此不是指数或阶乘增长。选择多项式来表示有效的计算似乎是任意的，然而，随着时间的推移，它从许多角度证明了自己的合理性。例如，多项式在加法、乘法和组合下的闭包保留了自然编程实践中的效率概念，比如将程序链接到一个序列中，或者将一个程序嵌套到另一个程序中

多年来，为了有效地解决哈密顿循环决策问题，科学家们进行了许多尝试。其中一种是Held-Karp算法，它能在指数时间内解决这个问题。然而，没有已知的算法可以在多项式时间内解决这个问题，因此，它仍然被认为是一个难题。

• 迈克尔·赫尔德，理查德·史克和理查德·卡普。

然而，一个有趣的现象发生了，尽管我们不能有效地解决这个问题，给定一个路径图中，我们至少可以有效地检查是否是哈密顿循环，因为简单循环中的最大顶点数为n，则遍历路径所需的时间被多项式限定为n。。

这种现象也出现在其他难题中，例如数独决策问题——给定一个不完整的数独网格，我们希望知道它是否至少有一个有效的解决方案。任何提出的数独解决方案都可以很容易地验证，并且随着网格的增大，检查一个解决方案的时间会多项式的增长。然而，所有已知的寻找解决方案的算法，对于困难的例子，时间会随着网格的增大呈指数增长。与哈密顿路径决策问题相似，目前还没有任何已知的算法可以有效地解决数独问题，但是，只要给出一个解，就可以有效地验证该解。似乎许多其他决策问题都具有这一特性——不管它们是否能被有效地解决，它们所提出的解决方案都能被有效地验证。这类问题被定义为NP。

文章来源：《生物数学学报》 网址: http://www.swsxxb.cn/zonghexinwen/2020/1109/367.html

上一篇：谈祥柏其人与他的数学科普
下一篇：动物界里的数学家都有谁？