1.5 漫漫长途

本书讲的是P和NP的故事。什么是P和NP?P/NP描述的是哪类问题?所有搜索问题中最难的问题——“NP完全问题”是怎么回事?这些问题如何影响P/NP问题?

举个简单的例子,Facebook上的好友圈子(即团,clique)中,最大的包含多少人?100人,还是1000人?即使你拥有Facebook的全部数据,这个问题也很难求解。求解较大规模团问题的困难程度,不亚于任何搜索问题。

如果P=NP会怎么样?那么我们将迎来一个美好的世界,计算所有的事物都将易如反掌。我们能快速地了解一切,揭开世界上所有事物的神秘面纱,从治愈绝症到洞悉宇宙的本质。美好的世界也有它灰暗的一面,人们将丧失隐私、丢掉工作,因为没有什么是计算机不能知道或完成的。

这样美好的世界几乎不太可能。困难的搜索问题仍将存在,我们想要甚至需要找到它们的答案。其实我们大可不必放弃。计算机科学家已研发出许多技术,包括很有可能对许多问题奏效的启发式方法,以及能给出接近理想解的近似技术。

P和NP问题是如何产生的?这个故事发生在世界因冷战被割裂的那段日子,其实可以把它分成两个故事来讲。有关高性能计算的思路和问题分别在两个世界独立发展,而这两个世界的研究最终殊途同归,从而产生了P/NP问题。

从哪里着手证明P≠NP?库尔特·哥德尔证明数学不能解决所有的问题。能否用类似的方法,证明存在不能快速解决的搜索问题?为了分析问题的复杂度,我们可以把计算过程分解为最基本的单元。算术几何学(数学的一个抽象分支),为人们能在有朝一日解决这个重要的问题带来了新的希望。但我们距离那一天还很远。

P≠NP会带来什么好处呢?它能帮助我们保守秘密,产生看上去真随机的伪随机数。

未来基于量子力学的计算机能否让P/NP问题变得无足轻重?不太可能,不过量子计算机的建成将解决一部分现在计算机束手无策的问题,比如大数的因数分解。此外,量子力学也会透露P是否等于NP的玄机。

未来将会如何呢?我们仍将面临计算领域的巨大挑战。人们如何与互相协作处理问题的计算机打交道?如何分析每天产生的海量数据?所有事物都能联网,世界将会怎样?要解决这些问题,P/NP问题只会变得更为关键。

目录