前言

近半数的美国人都拥有智能手机。智能手机也是计算机,其计算能力比几十年前的超级计算机还要强。计算机将世界上的信息呈现在我们眼前,也帮我们梳理信息。计算机让人们可以彼此交流,无论什么身份,地处何方。计算机能执行数量巨大的运算,从模拟宇宙事件到调度复杂的航线。计算机可以识别人的声音、面孔和动作。计算机可以获悉人们的喜好,并据此推荐图书、音乐和电影。在不远的将来,借助计算机技术,无人驾驶的汽车将随处可见。这么说,计算机简直无所不能。

真是这样吗?在这本书里,我们将探讨许多计算问题,其中一部分可能永远都无法用简单的计算得到答案。试着解答它们是计算机科学,乃至整个数学和科学领域最重要的挑战。人们给这些问题起了一个有些奇怪的名字:P/NP问题。

P/NP是克雷数学研究所公布的7个千禧年数学难题之一,该研究所为求解这道难题设立了百万美元的奖金。不过,P/NP问题的意义远不止于此。

P指的是用计算机能很快求解的问题,NP指的是我们想找到最优解的问题。如果P=NP,那么我们将很容易找到任意给定问题的解。P=NP意味着我们所了解的社会将发生巨变,医学、科学、娱乐和人类社会一切任务的自动化程度都将立即发生质的飞跃。

相反,如果P≠NP,那么总会有部分问题无法迅速地被解决。那也没有关系,因为我们可以根据具体情况研发出某些技术来解决这些问题。P≠NP意味着不可能用自动化的方法解决所有问题。然而,知道哪些工具不好用也有助于人们找到更好用的工具。

2008年8月,《ACM通讯》的主编莫舍·瓦迪约我写一篇关于P/NP问题的文章。ACM(美国计算机协会)是一个为计算机研究学者和从业人员服务的重要社团,《ACM通讯》则是该协会刊登文章的主要杂志。

一开始我想把写稿的事推给另一位计算机科学家,但后来我还是答应了。当时莫舍是这么劝说我的:“如果那帮物理学家可以写关于弦理论的畅销文章(和图书),那我们也可以向公众解释计算复杂度理论目前的进展,我希望如此。”于是我写了一篇文章,该文章以《ACM通讯》的读者为主要受众,不仅介绍了P/NP问题的现状(基本可以概括为“悬而未决”),也讲了一些人们在处理困难问题时积累的技巧。“P/NP问题的现状”(The Status of the P versus NP Problem)发表在2009年9月的《ACM通讯》上,它很快就成为该刊物创刊以来下载次数最多的文章。

关于P/NP问题,我觉得还有很多故事可讲,而那篇文章的大受欢迎,似乎表明是时候面向更广的受众(而不仅是科学家们)来讲述这些故事了。

我将那篇短文作为本书的框架结构,将原来文章的各个部分扩展为现在的章节。我还受到了史蒂芬·霍金的《时间简史》的启发:该书尽量绕开晦涩的公式和术语,采用生动的例子和故事来解释物理。我试图以同样的方式来讲解P/NP问题,借此探讨P/NP问题的本质和重要意义。

本书没有给出P/NP问题的正式定义,有很多教科书和网站都详细论述了P和NP的定义及技术结论。本书旨在让你对计算科学的潜能和局限性有更多的了解,这非常有好处,毕竟计算机如今已成为人类生活不可或缺的部分了。

向P和NP进发吧!

兰斯·福特诺

于伊利诺伊州埃文斯顿

目录