本书讲的是P和NP的故事。什么是P和NP?P/NP描述的是哪类问题?所有搜索问题中最难的问题——“NP完全问题”是怎么回事?这些问题如何影响P/NP问题? 举个简单的例子,Facebook上的好友圈子(即团,clique)中,最大的包含多少人?100人,还是1000人?即使你拥有Facebook的全部数据,这个问题也很难求解。求解较大规模团问题的困难程度,不亚于任何搜索问题。 如果 会怎么样?那么我们将迎来一个美好的世界,计算所有的事物都将易如反掌。我们能快速地了解一切,揭开世界上所有事物的神秘面纱,从治愈绝症到洞悉宇宙的本质。美好的世界也有它灰暗的一面,人们将丧失隐私、丢掉工作,因为没有什么是计算机不能知道或完成的。 这样美好的世界几乎不太可能。困难的搜索问题仍将存在,我们想要甚至需要找到它们的答案。其实我们大可不必放弃。计算机科学家已研发出许多技术,包括很有可能对许多问题奏效的启发式方法,以及能给出接近理想解的近似技术。 P和NP问题是如何产生的?这个故事发生在世界因冷战被割裂的那段日子,其实可以把它分成两个故事来讲。有关高性能计算的思路和问题分别在两个世界独立发展,而这两个世界的研究最终殊途同归,从而产生了P/NP问题。 从哪里着手证明 ?库尔特•哥德尔证明数学不能解决所有的问题。能否用类似的方法,证明存在不能快速解决的搜索问题?为了分析问题的复杂度,我们可以把计算过程分解为最基本的单元。算术几何学(数学的一个抽象分支),为人们能在有朝一日解决这个重要的问题带来了新的希望。但我们距离那一天还很远。 会带来什么好处呢?它能帮助我们保守秘密,产生看上去真随机的伪随机数。 未来基于量子力学的计算机能否让P/NP问题变得无足轻重?不太可能,不过量子计算机的建成将解决一部分现在计算机束手无策的问题,比如大数的因数分解。此外,量子力学也会透露P是否等于NP的玄机。 未来将会如何呢?我们仍将面临计算领域的巨大挑战。人们如何与互相协作处理问题的计算机打交道?如何分析每天产生的海量数据?所有事物都能联网,世界将会怎样?要解决这些问题,P/NP问题只会变得更为关键。
可能与不可能的边界——1.5 漫漫长途
书名: 可能与不可能的边界
作者: [美] Lance Fortnow
出版社: 人民邮电出版社
原作名: The golden ticket:P,NP,and the search for the impossible
副标题: P/NP问题趣史
译者: 杨 帆
出版年: 2014-1
页数: 160
定价: 39.00
装帧: 平装
ISBN: 9787115335661