第7章　证明P≠NP

    尤里斯·哈特马尼斯是计算复杂度理论的奠基人之一，他曾说：“我们都知道P和NP不一样，但就是不知道如何证明这一点。”

    我们在前面几章中从多方面探讨了P/NP问题，包括它是什么，它的研究意义，P=NP的虚幻美妙世界，以及如何处理由P≠NP带来的困难问题。

    P/NP问题也是一个迷人而富有挑战性的数学问题。从库克、卡普和莱文将这个问题及其重要意义呈现给世界的那一刻起，计算机科学家和数学家就一直努力形式化地证明P=NP或P≠NP。但所有常规的手段都失效了。到20世纪70年代末，大家达成的共识是“P/NP问题的解决可能有赖于大幅度创新的证明技术”。

    第7章 证明P≠NP - 图1

    图7-1　DILBERT © 1997 Scott Adams。使用需得到UNIVERSALUCLICK的许可，版权所有，侵权必究

    接下来的几十年中，计算机科学和数学都取得了不可思议的进步，包括解决了所有未解决数学问题中最著名的一个——费马大定理。1637年左右，法国律师兼数学爱好者皮埃尔·德·费马在他的《算术》（一本古希腊教科书）的书页边缘上写下如下这样一段文字：

    将一个立方数分成两个立方数之和，或一个四次幂分成两个四次幂之和，或更一般地，将一个高于二次的幂分成两个同次幂之和，都是不可能的。对此我确信已发现了一种美妙的证明方法，可惜这里空白的地方太小，写不下。

    也就是说，不存在大于0的三个自然数a、b和c，以及大于2的自然数n，能令an+bn=cn。费马再也没有提到这个定理的证明方法，也有可能他压根就没想出正确的证法。后来这个问题闻名于世，成为一个经典的数学未解之谜。我小时候也梦想成为第一个解决这个著名问题的人。另外一个和我有着共同梦想的小孩长大后实现了他的梦想。1994年，普林斯顿大学的数学家安德鲁·怀尔斯在前人发表的一系列有关数论的论文基础上，构造出了费马定理的证明。他立刻成了名人，至少拥有了作为一个数学家所能够享有的无上荣耀。

    这一章不会告诉你如何解决P/NP问题，否则这将是一本非常不同的书。我们只会介绍一些人们在尝试解决P/NP问题时曾经产生过的想法。可惜，这些想法没能让我们距离解决该问题更近一点。要证明P≠NP，就要证明不存在能解决某些NP问题的算法（甚至包括那些未被发现的算法）。很难去证明不可能做成某件事，尽管这在逻辑上并非不可能。所以，对于这个也许是所有数学问题中最为重要同时最具挑战性的问题，我们还是希望看到它被解决的那一天。