19、P=NP？（1/1）
科学的逻辑19、P=NP？：准备有声小说在线收听
美国克雷数学研究所于2000年选出了千禧年七大数学难题，解决任意一个难题都可以获得100万美元的奖励。如今，只有庞加莱猜想被佩雷尔曼证明，而其它六个仍然吸引着大量数学家的目光。在这六个千禧难题中，有一个显得格外引人注目，那就是P/NP问题。因为一旦证明等式成立，其它五个千禧难题也将迎刃而解，世界也将变得格外不同且奇妙无比。即使证明了等式不成立，也会让我们认识到，世界可能比我们想像的更复杂，从而改变研究问题的方向，避免大量的数学家徒劳的努力。
在计算机科学领域，存在一个叫做计算复杂度的概念。也就是说，随着问题规模的增加，计算量以怎样的方式增长。计算机有极高的运行速度，因此如果计算量增加的规模是问题规模的多项式函数，即当问题规模用n表示时，多项式函数可理解为n的k次方，那么多项式级别的增长速度是计算机可以接受的，也就是说，问题是容易解决的。而如果计算量是问题规模的指数函数，则一般会耗尽计算机的运算能力，使之需要天文数字的计算时间，导致问题变得实际上不可解。
依据计算复杂度的不同，可以将问题集合进行分类。如果某个问题可以容易的求出解（在多项式时间内），我们把它称之为P类问题。如果某类问题的求解不能或暂时不能找到简单的算法，但是一旦给出一个解，我们可以容易的（在多项式时间内）验证它的确就是该问题的解，我们将它称之为NP类问题。就像在科学探索的过程中，我们花费了大量的时间和精力仍然无法发现真理，而牛顿和爱因斯坦的理论一经发表，我们可以很快的知道，这就是我们要找的东西。问题容易求解显然也容易验证，因此，P问题是NP问题的子集。NP问题有很多经典的例子。像旅行推销员问题：存在n个城市，推销员从某个城市出发，怎样走才能访问所有城市，而且做到既没有重复的城市，又能让旅途路程最短？显然，他需要从（n-1）！种可能中寻找，当n很大时，阶乘函数很快成为指数级的天文数字，导致问题难以求解。还有像大数的因式分解问题，将两个大素数相乘很简单，但把这个合数分解成两个大素数的乘积就困难多了。它们都属于NP问题。然而，这两个问题或许存在某种重要的区别。
1971年，库克发表了一篇重要的论文，他告诉我们，所有的NP问题都可以归约到一个被称之为可满意性问题的概念上，通俗说就是可满意性问题是所有NP问题中最难的一个，而且一旦这个问题能在多项式时间内解决了，其它所有NP问题都能被轻易的解决，而这个可满意性问题被称为NPP完全问题。因此，问题变成了P=NP？更有意思的是，卡普发现，NPC问题不止一个，至少他找到了21个（其中就包括旅游推销员问题），它们来自千差万别的不同领域，看似风马牛不相及，却彼此等价。卡普的工作激发了人们寻找NPC问题的热潮，最终，数学家们发现了几千个NPC问题，它们都彼此等价，一旦证明这几千个NPC问题中的任何一个可以找到多项式时间内的算法，也就证明了P=NP，反之，若不存在这样的算法，则它们不相等。
如果P=NP，那么意味着什么呢？它会告诉我们这个世界的一个大秘密：容易验证的问题同样也是容易求解的。许多不同领域的问题可以通过计算机在短时间内解决，数学的、物理的、生物的、化学的、经济学的、心理学的……所有的几千个NPC问题都将被解决；许多经典游戏像数独、扫雷、俄罗斯方块都将失去乐趣；计算机可以轻松通过图灵测试，甚至比人更聪明；人们可以根据每个人的基因不同开发针对个人的药物，用于治疗包括癌症在内的大量疾病；可以更精确的进行长期天气预报；可以让计算机写出优美的文学作品，创作音乐和绘画；可以破译任何密码……基于这样美好的世界不太可能是真的，大多数计算机科学家都认为P=NP不成立，但目前还没有人能证明这一点。
值得一提的是，基于量子力学的量子计算机具有常规计算机难以企及的并行处理能力，从而可以大幅度提高计算效率。尽管量子计算机目前还存在很多技术上的困难而难以普及，但至少已经不存在理论上的困难了，实用量子计算机的出现或许只是时间问题。那么基于量子力学神奇的效应，有没有可能通过在量子计算机上运行量子算法来实现P=NP呢？1994年，肖尔提出了一种量子算法，可以在多项式时间内解决大数的因式分解问题，肖尔把一个NP问题转化为了P问题，让目前为止广泛应用的RSA公钥密码体系面临崩溃的边缘。可惜的是，目前还没有人能证明大数因式分解是NPC问题，大数因式分解的确很难，但似乎还没有达到NPC的难度，因此量子计算是否能证明或证伪P=NP还是未知数。
如果我们足够幸运，世界是P=NP的，那么我们的精力必然会转向一类新的问题：NP-hard。它的意义是，当所有的NP问题都可以归约到一个问题时，也就是说一旦这个问题有多项式解法，所有NP问题也都解决了时，这个问题就叫NP-hard，该问题不一定是个NP问题。显然，NPC是它的一个子集，该问题集比NPC还难，至少一样难，有时连验证一个解都是困难的，常见的NP-hard例子有围棋、停机问题等。
P/NP问题的诱人前景吸引了一批又一批的数学家和计算机科学家投身其中，问题的解决可能在明天，也可能需要几个世纪，问题的答案似乎触手可及，又似乎远在天边。无论问题能否被解决，至少我们探索未知的脚步都不会停止。