P=NP是真实存在的麽？

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

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

二维平面图形的十二面体。一个可能的哈密顿循环用红色表示。给出一个图，确定它是否包含一个哈密顿循环。

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

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

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

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

具有多项式时间复杂度的算法被称为“高效”。

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

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

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

如果一个决策问题的解能被有效地验证，那么这个决策问题就是NP问题。

首字母缩写NP代表不确定性多项式时间（尽管人们普遍认为NP的意思是“非P”）。

进一步思考问题的可解性与其解的可验证性之间的关系，我们可以得出下一个结论：如果一个决策问题是有效可解得，那么它的解必须是有效可验证的。为什么？因为如果一个决策问题是可以有效地解决的，那就意味着我们可以有效地找到它的解决方案。然后，给出一个解决方案，我们可以简单地通过与问题的实际解决方案比较来验证它。换句话说，生成解决方案的算法的正确性自动证明了该解决方案。从这个结论可以看出，很明显，NP包含的问题子集也是有效可解的。这个子集被定义为P。

P是所有可有效解决的决策问题的集合，是NP的一个子集。基本算法是多项式时间可解的。象棋决策问题不属于NP问题，因为没有一种有效的算法可以检查给定的棋盘是否有效。魔方决策问题属于NP问题，因为判断一个给定的魔方是否是一个解是很简单的。哈密顿路径决策问题有一个有效的算法可以验证它的解，因此，它属于NP。有人可能会问这个问题是否在P中，一方面，我们不知道有一个有效的算法可以解决这个问题。另一方面，没有证据表明这样的算法不存在。事实上，这样的算法仍然有可能存在，而且还没有被发现。数独的决策问题也是一样，事实上，对于许多其他主要问题，包括布尔可满足性问题，旅行推销员问题，子集和问题，派系问题，图着色问题——尽管我们已经证明这些问题是NP，但没有证据表明他们在P 。这就是P=NP问题的意义所在：

P和NP真的是一样的吗？如果是的话，这就意味着NP中的所有问题都可以被有效地解决，尽管我们仍然没有找到实现这一点的神秘算法。否则，在NP中存在一些无法有效解决的问题，任何尝试解决将意味着浪费我们的时间和精力。

大多数时候，不能有效地解决问题是一件消极的事情。然而，在某些情况下，我们可以从问题的“硬度”中获益。属于NP而不属于P的问题，其主要特点是很难解决，但很容易验证其解决方案。

给定两个正整数n和k，判断n是否有一个质因数小于k。——质因数分解决策问题

由于该问题的解可以有效地验证，因此我们知道该问题属于NP，给定一个整数c，它需要“多项式时间”来知道c是否是一个比k小的质数，还是n的因数。但是，目前还没有一种算法可以在多项式时间内解决这一问题。因此，使用两个相当大的质数，就可以计算它们的乘法，这用于生成一个公钥和一个私钥。公钥可以为所有人所知，并用于加密消息。使用公钥加密的消息只能在合理的时间内使用私钥解密，假设没有有效的方法将一个大整数分解为它的质数因子。

RSA-2048有617位十进制数字(2048位)。它是RSA数字中最大的，因式分解获得的现金奖金最高，为20万美元。除非在不久的将来在整数因子分解或计算能力方面取得重大进展，否则RSA-2048在许多年内可能无法分解。但是，如果P=NP，则最后一个假设是错误的。为什么？如果P等于NP，那么质因数分解问题在P中，这意味着它可以被有效地解决。因此，一旦找到这样一个算法，任何公钥都可以在合理的时间内解密，而不需要私钥，这使得整个RSA密码系统完全崩溃，至少在理论上如此。

但是P=NP的负面影响与它所具有的潜在好处相比，是无关紧要的。在数学、优化、人工智能、生物学、物理学、经济学和工业领域中，确实存在着数以千计的NP问题，这些问题都是出于不同的需要而自然产生的，而有效的解决方案将使我们在许多方面受益。证明P=NP将意味着所有这些难题都可以在多项式时间内解决，这将导致在那些卓越的算法之后进行大规模的智力追求。一旦发现，这些算法将有可能推动人类的进步，远远超出我们的掌握。

Christian Boehmer Anfinsen是1972年诺贝尔化学奖的获得者之一，因为他致力于研究一种小的，耐久的100个氨基酸长的蛋白质核糖核酸酶A的折叠。该蛋白质折叠问题是一个NP问题。即使这样的结果，与解决NP问题的有效方法在数学本身引起的革命相比，也可能显得微不足道。

以著名的毕达哥拉斯定理为例，该定理阐述了直角三角形的直角边和斜边之间的关系。这个定理有370个已知的证明。这些证明都是下列决策问题的一个可能的解决方案：“勾股定理是正确的吗?”这个想法可以概括为：

如果T是一个定理，p是它的证明，那么p是决策问题的一个解：“T正确吗？”

数学定理与决策问题之间的这种关系允许我们推广关于P与NP的讨论——如果一个证明的正确性可以在多项式时间内得到验证，那么相应的决策问题就是NP问题（因为证明是对该决策问题提出的解决方案）。在一个P等于NP的世界里，这样一个决策问题在P中，这意味着它可以用多项式时间来解决。解决这样一个决策问题本质上就是找到定理T的证明。这可能意味着，在某种程度上，证明一个数学定理并不比检查一个给定证明的正确性难多少。

P = NP可能意味着证明一个数学定理从根本上来说并不比验证其证明的正确性更难。

最后的结论是值得注意的，因为每一个数学证明都可以形式化为一系列定义良好的逻辑陈述，并由计算机程序进行处理，自动验证证明。因此，P = NP意味着证明数学定理可以用一个简单的计算机程序来完成。

“P = NP可以通过允许计算机找到任何定理的形式证明来改变数学，只要这个定理能证明一个合理的长度，因为形式证明可以在多项式时间内很容易地被识别出来。”——斯蒂芬·库克

人们认为P=NP不太可能的一个心理原因是，提出数学定理这样的任务通常需要一定程度的创造力，而我们并不指望一个简单的计算机程序具有这种创造力。

我们欣赏维尔斯关于费马最后定理的证明以及牛顿，爱因斯坦，达尔文，沃森和克里克的科学理论，欣赏金门大桥和金字塔的设计，有时甚至是赫尔克里·波洛和马普尔小姐对谋杀案的分析。正是因为他们似乎需要一个飞跃，这不是每个人都能做到的，更不用说简单的机械设备了——阿维·威格森

以上的观点让我们开始讨论人类大脑的本质。虽然科学离理解大脑的机制还很遥远，但物理定律控制着它的行为。因此，就像其他自然过程一样，大脑是一种高效的计算设备。因此，任何解决任何问题的方法只要被大脑识别，就可以被有效地识别。因此，P=NP可能意味着大脑有能力以同样的效率解决这些问题。

如果P = NP，那么任何人类或计算机都将拥有传统上被认为是神的那种推理能力，这似乎很难接受。

对于大多数人来说，像怀尔斯对费马最后定理的证明或爱因斯坦的相对论这样的惊人发现可以由一个没有头脑的机器人产生是不可能的，因为他们都有一个强烈的观点，即创造力对于获得这样的见解是绝对必要的。

如果P=NP，那么这个世界将是一个与我们通常假设的完全不同的地方。每个能欣赏交响乐的人都会是莫扎特。”——Avi Wigderson

复杂性理论家普遍认为P不等于NP，这样一个美丽的世界是不可能存在的。2000年，克莱数学研究所将P与NP问题列为数学中七个最重要的开放问题之一，并为能证明P是否等于NP的问题提供了100万美元的奖金。