可能与不可能的边界[试读]
1.1 划分的难题
一个糖果厂老板决定推出一个活动，将五张金券藏到巧克力的包装里，而这种巧克力每年的产量数以千万计。找到金券的人将得到一次珍贵的参观工厂的机会。 如何找到这些金券？你可以买尽可能多的巧克力。你可能会试试用磁铁，可惜金没有磁性。或者你可以雇用数千人，让他们每人筛查一小堆巧克力。这听起来很傻，但是小姑娘维露卡•索尔特就要这么做，因为她特别想得到一张金券，去参观威利•旺卡的巧克力工厂。 维露卡的父亲索尔特先生是个富商，他决定买光他能找到的巧克力。这还不够，就算有堆积如山的巧克力，要从中找到小小的金券也很困难。索尔特先生也有一家工厂，他不惜动用工厂的工人，终于找到了一张金券。他对记者讲述了找到金券的过... 查看全部[ 1.1 划分的难题 ]
1.2 手
你的手是最不可思议的工程装置，它能戳、抓和指，能系鞋带，能射箭，还能弹钢琴、拉小提琴，能变戏法，能驾驶车、船、火车或飞机。你的手可以握住其他人的手，或跟他们玩拇指相扑。手可以比划出信号语言，也能通过写字或打字来交流。手可以轻抚，也能重击。手可以使用修理钟表的精密工具，也能操作链条锯。有才华的人的双手可以创造艺术杰作，写出音乐或诗歌。人类取得的几乎所有成就，都离不开双手。 一只手有27块骨头，5根手指，包括最重要的拇指。手具有结构复杂的神经、肌腱和肌肉，这些都包裹在富有弹性的皮肤里。然而，这一不可思议的装置，自然造物的杰作，却不能自己做事，而只能执行人脑的指令。死人的手平平无奇，做不了任何事情... 查看全部[ 1.2 手 ]
1.3 P/NP问题
P/NP问题讨论的是以上所述的所有问题，以及许多与之类似的问题。它们归根到底都是在问：我们搜索大量可能性的速度能有多快？我们找到“金券”（即最佳答案）的过程能变得多容易？ P/NP问题是库尔特•哥德尔在1956年寄给约翰•冯•诺依曼的一封信中首次提出的，哥德尔和冯•诺依曼都是20世纪数学界的泰斗。这封信后来不幸遗失，20世纪80年代又被找到。P/NP问题在学术界的亮相是在20世纪70年代初，由斯蒂芬•库克和列昂尼德•莱文独立提出，当时两位所在的国家正在冷战。之后理查德•卡普列出了这个领域中的21个重要难题，包括前面提到的旅行推销员难题和划分难题。计算机科学家从卡普的工作开始认识到P/NP问题... 查看全部[ 1.3 P/NP问题 ]
1.4 找到金券
有时候我们能够找到金券。比如我在芝加哥，想开车去纽约，往车载GPS里输入地址，一两分钟之内它就能给出一条从芝加哥到纽约的最快路线，然后我就可以踏上旅程了。几百万字节的内存便可容纳全部的美国街道地图，但地图中可能的路线远远超过几百万。从芝加哥到纽约所有可能的行车路线有多少条？不开错方向的情况下，保守计算可得出的路线数目大到了“不可思议”，即1后边跟63个0。GPS根本没有时间检查所有的可能性，但还是能找到最快的路线。 旅行时间有一个有趣的性质。随便选一个中间地点（比如匹兹堡），从芝加哥经过匹兹堡到纽约的最短路线，一定是芝加哥到匹兹堡的最短路线，再接上匹兹堡到纽约的最短路线。不走匹兹堡可能有更快... 查看全部[ 1.4 找到金券 ]
1.5 漫漫长途
本书讲的是P和NP的故事。什么是P和NP？P/NP描述的是哪类问题？所有搜索问题中最难的问题——“NP完全问题”是怎么回事？这些问题如何影响P/NP问题？ 举个简单的例子，Facebook上的好友圈子（即团，clique）中，最大的包含多少人？100人，还是1000人？即使你拥有Facebook的全部数据，这个问题也很难求解。求解较大规模团问题的困难程度，不亚于任何搜索问题。 如果 会怎么样？那么我们将迎来一个美好的世界，计算所有的事物都将易如反掌。我们能快速地了解一切，揭开世界上所有事物的神秘面纱，从治愈绝症到洞悉宇宙的本质。美好的世界也有它灰暗的一面，人们将丧失隐私、丢掉工作，因为没有... 查看全部[ 1.5 漫漫长途 ]
1.6 划分难题的解
以下38个数 14 175, 15 055, 16 616, 17 495, 18 072, 19 390, 19 731, 22 161, 23 320, 23 717, 26 343, 28 725, 29 127, 32 257, 40 020, 41 867, 43 155, 46 298, 56 734, 57 176, 58 306, 61 848, 65 825, 66 042, 68 634, 69 189, 72 936, 74 287, 74 537, 81 942, 82 027, 82 623, 82 802, 82 988, 90 467... 查看全部[ 1.6 划分难题的解 ]
书名： 可能与不可能的边界
作者： [美] Lance Fortnow
出版社： 人民邮电出版社
原作名： The golden ticket:P,NP,and the search for the impossible
副标题： P/NP问题趣史
译者： 杨 帆
出版年： 2014-1
页数： 160
定价： 39.00
装帧： 平装
ISBN： 9787115335661