np是什么意思呢 数学中的最著名的难题P=NP

np是什么意思呢

今日小经验分享：数学中的最著名的难题P=NP和np是什么意思呢方面的经验，接下来带大家一起了解。

从历史的开端，人类就一直在是解决各种问题。从早期农业到太空探索，解决数学问题似乎是人类生存的一个关键因素。

自上世纪70年代以来，一些曾经单调乏味的计算问题在一瞬间就可以解决，这主要是由于计算能力的指数级增长。

然而，一些独特的问题仅仅通过技术进步是无法解决的，即使对于最强大的计算机来说，解决这些问题所花费的时间比人的一生还要长。

事实上，现代加密技术依赖于这样一个事实：大质数不可能因式分解。这些问题似乎都有一个共同的难题，也就是P（ polynomial time）对NP（ non-deterministic polynomial time）谜题的核心——什么是可化简的，什么是不可化简的？

1859年，爱尔兰数学家威廉·汉密尔顿画了一个叫做伊科希的数学游戏。这个游戏是在一个由20个角（顶点）组成的木制十二面体表面上进行的。每个角落都标上了一个城市的名字。

游戏的目标是找到一个循环，即访问每个顶点一次，然后返回起点。这种路径称为哈密顿循环。这个简单的博弈产生了图论中的一个重要问题，即哈密顿循环决策问题——给定一个任意地图，我们如何知道它是否包含一个哈密顿循环？

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

给出一个图，确定它是否包含一个哈密顿循环。

解决这个问题的一种方法是遍历图中任何可能的路径，并检查该路径是否为哈密顿循环。然而，由于可能路径的数量可以达到n的阶乘。

这样，即使一个只有40个顶点的图也可能包含超过10^45条路径，使得问题几乎不可能在合理的时间内解决(即使对于最强大的处理器也是如此)。

此外，由于顶点数量与路径数量之间的阶乘依赖关系，即使我们再增加一个顶点，也需要大幅提升计算机的计算能力。我们可以说，阶乘增长的根本性质使这个问题比其他问题更困难。

这就是数学问题的艰巨性——如果一个问题需要的资源随着投入的增加而急剧增加，那么这个问题就非常棘手。

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

渐进观点是计算复杂性理论所固有的，它揭示了有限而精确的分析所掩盖的结构——阿维·威格森