7.3　证明P≠NP时常犯的错误

2010年8月6日，惠普实验室的科学家维纳里·德奥拉利卡向22位顶尖的理论计算机科学家发送了他写的论文，题目简洁有力：“P≠NP”。曾经有许多追逐名利（克雷数学研究所提供的百万奖金）的人给出了P/NP问题的各种“证明”，他们认为P≠NP或P=NP，或者不可能判定P是否等于NP，或者声称P/NP问题根本就毫无道理。每年都会涌现很多这类证明的手稿，有的被发送到计算机科学家的电子邮箱里，有的被提交到学术期刊，还有的直接公布在互联网上。最著名的计算机科学期刊持续地收到声称解决了P/NP问题的来稿，后来，该期刊宣布了一条对这些文章的特殊规定。

The Journal of the ACM（JACM）经常收到来稿，声称解决了复杂度理论领域一个长期悬而未决的问题，即P/NP问题。这些来稿严重占用了JACM自愿提供的编辑和审查资源，因为需要一定的时间才能辨识其中的错误。JACM仍然对P/NP及相关问题的解决保持开放的心态，并将继续欢迎针对这个主题的投稿。然而，为了减轻由屡次重复提交并逐一订正错误而带来的负担，本刊决定采取如下规定：对于P/NP这个复杂度理论领域长期未解决的问题或与之相关的主题，任何作者在24个月的周期内只能提交一篇文章，除非受到主编的约稿。此规定也适用于之前被拒稿件的再次提交。

在这些对解决P/NP问题的尝试中，大部分要么不知所云，要么明显是错误的，学术界对此基本上视而不见。而德奥拉利卡的文章则受到了特殊的待遇。他本人在过去曾发表过研究论文，并且这篇论文的写作水平超出了大部分的P/NP投稿。于是有的理论学家感到有必要仔细研读一下这篇论文。这在互联网上引起了轩然大波，一些微博和博客甚至急不可耐地提前宣布P/NP问题得到了解决。几个著名的计算机科学家和数学家在仔细研读了德奥拉利卡的论文后，发现了其中的几处缺陷，有一些是小疏漏，另一些则是大错特错。8月16日，也就是论文公布后的第10天，纽约时报发表了一篇文章来描述事件的整个过程，标题是“第1步：发布模棱两可的证明；第2步：欣赏烟火表演”（Step 1: Post Elusive Proof. Step 2: Watch Fireworks）。此时学术界的一致意见是该证明是错误的，且没有修改的余地。P/NP问题的状态仍然是悬而未决。

希望这本书能让许多读者了解到P/NP问题的重要性，并且对解决这个问题跃跃欲试。我鼓励你试试，因为如果不亲自尝试，很难真正理解一个问题是多么困难。要注意本书并未正式地定义P/NP问题，如果读者真的想求解这个问题，首先要了解其最准确的表述。本书的网站上提供了几个很好的资源，供读者了解P/NP问题和各种求解尝试的技术细节以及公理化描述。

假设你真的找到了P/NP问题的解决方法，该怎么通知克雷数学研究所，让他们把一百万美元的支票寄过来呢？先别急。你几乎不可能有合理的证明。通过了解为什么你的证明可能不行，你说不定会得到启迪。

下面我就描述一下那些认为自己证明了P/NP问题的人通常会犯哪些错误。

早在1550年，意大利数学家吉罗拉莫·卡尔达诺给出了可能是第一个P≠NP证明的反面例子。卡尔达诺被认为是概率论领域的奠基人之一，在宣传他发明的一种新的加密系统时，他声称该系统绝对安全，因为密钥太多，无法逐个检查。实际上这个系统非常容易破解，因为对加密的消息做解密分析时根本不需要检查所有的密钥。

类似卡尔达诺所犯下的根本性错误，在现在证明P≠NP的尝试中屡见不鲜。再次考虑团问题。一类证明的思路是，任何试图求解团问题的算法在找不到一个有效解时，都必须确保不可能存在给定人数的团。唯一可行的方式是检查所有可能的人组成的集合，然后检查给定的集合是否成团。由于集合太多了，任何算法都必须花费特别长的时间。所以团问题不存在高效的解法。故P≠NP。Q.E.D.（Q.E.D.是拉丁短语quod erat demonstrandum的缩写，意为“要展示的就是这么多”，常用于数学证明的结尾，表示证明完毕。）

这种思路有很多的变种。而其中的逻辑漏洞在于“唯一可行的方式”。算法可行的方式也许非常难以捉摸。它并不需要按你认为的方式工作，甚至完全不用遵守问题本身的内在结构。也许有一个算法，把好友关系图转化成某些奇怪的代数表达式，当且仅当团存在时才存在某一类型的解。虽然这不太可能，但是不能因为你认为算法不这样工作，就排除它存在这样的可能性。

很难让使用这种证明技巧的人相信他（或者她，但是给出这些糟糕证明的人几乎无一例外全部都是男性）是不对的。他们总会反过来要我写出一个不用穷举就能解出团问题的算法。我当然写不出来，能写出来不就意味着P=NP了嘛，况且这不太可能是真的。但证明的负担在你身上，要主张你给出的证明的合理性，你需要论证不存在以其他方式工作的算法。

而要证明P=NP,“只需”给出某个NP完全问题的有效算法。于是很多人会给出团问题的一个算法，然后就说他们证明了P=NP。但是一个算法本身并不构成一个证明。必须还要形式化地论证该问题的每一个实例，即在所有可能的好友关系图上，该算法都能高效地运行，并给出正确的答案。而这些证明的尝试要么没有覆盖所有可能的情况，要么本身就是错误的或不完整的。给出的算法不是结果是错误的，就是在复杂的实例上无法高效地运行。