可能与不可能的边界

第1章　金券　　1
维露卡的父亲索尔特先生是个富商，他决定买光他能找到的巧克力。这还不够，就算有堆积如山的巧克力，要从中找到小小的金券也很困难。
1.1 　划分的难题　　3
1.2 　手　　4
1.3 　P/NP问题　　5
1.4 　找到金券　　6
· · · · · · (更多)

第1章　金券　　1
维露卡的父亲索尔特先生是个富商，他决定买光他能找到的巧克力。这还不够，就算有堆积如山的巧克力，要从中找到小小的金券也很困难。
1.1 　划分的难题　　3
1.2 　手　　4
1.3 　P/NP问题　　5
1.4 　找到金券　　6
1.5 　漫漫长途　　7
1.6 　划分难题的解　　8
第2章　美妙的世界　　10
“不完全准确，”医生说，“没错，厄巴纳算法帮人们战胜了癌魔，治愈了艾滋病和糖尿病。可是，我们还不知道如何应对普通感冒。”
2.1 　厄巴纳算法　　10
2.2 　计算机1，癌症0　　13
2.3 　棒球比赛　　14
2.4 　奥卡姆剃刀　　17
2.5 　创造力的自动化　　21
2.6 　终极侦探　　22
2.7 　美妙世界的阴暗面　　23
2.8 　回到现实　　24
第3章　P和NP　　25
1852年，南非数学家弗朗西斯?格思里在为英国各郡的地图填色时，猜想是否只用四种颜色，就足够让所有地图上每两个接壤的地区有不同的颜色。
3.1 　敌友国　　25
3.2 　六度理论　　25
3.3 　牵线搭桥　　28
3.4 　团问题　　31
3.5 “递棍儿”　　32
3.6 　刷房子　　36
3.7 　分组　　38
3.8 　P和NP　　39
3.9 　敌友国之外　　40
3.10 　Icosian游戏的一个解　　43
第4章　NP中最难的问题　　44
高德纳对这个民选结果不太满意，但也没有觉得它差到让人活不下去的地步。他本人特别想要找一个英文词，既能捕捉“困难的搜索问题”这个直观的意象，又要琅琅上口，便于向大众普及。
4.1 　第一个NP完全问题　　44
4.2 　21个问题　　47
4.3 　起个好名字有那么重要吗　　49
4.4 　超越卡普的工作　　51
4.5 　漏网之鱼　　57
第5章　P和NP诞生前的历史　　62
图灵在1936年就指出，图灵机并不是什么都能计算。最著名的例子是停机问题，即没有计算机能通过查看一段代码就知道自己是会永远执行下去还是会最终停止。
5.1 　西方　　63
5.2 　东方　　68
5.3 　哥德尔的信　　74
5.4 　火星人法则　　74
第6章　处理困难的问题　　76
有时候一个问题天生排斥任何可能解决它的方法，对此你能做的只有放弃，然后去干点别的。
6.1 　蛮力　　77
6.2 　启发式方法　　78
6.3 　搜索小规模的解　　83
6.4 　近似计算方法　　85
6.5 　解决一个不同的问题　　90
6.6 　接受现实　　92
6.7 　总结　　92
第7章　证明 　　94
2010年8月6日，惠普实验室的科学家维纳里?德奥拉利卡向22位顶尖的理论计算机科学家发送了他写的论文，题目简洁有力：“ ”。
7.1 　骗子悖论　　95
7.2 　电路　　97
7.3 　证明 时常犯的错误　　102
7.4 　现状　　104
第8章　秘密　　106
每个人都有秘密，从密码到电子邮件，我们都有不想让别人看到的东西。 意味着某些NP问题拥有不为人知的秘密，无法很快找到它的答案。
8.1 　经典密码学简史　　106
8.2 　现代密码学　　108
8.3 　 下的密码学　　111
8.4 　零知识数独　　112
8.5 　玩游戏　　117
8.6 　在云上进行加密计算　　119
8.7 　创造随机性　　120
8.8 　持续的挑战　　121
第9章　量子　　123
即使有极小部分的量子和外界环境发生轻微作用而丧失了纠缠态，从另一头出现的我就很可能被毁形，甚至变成一团死肉。
9.1 　量子录像机　　123
9.2 　量子密码学　　127
9.3 　量子隐形传输　　128
9.4 　量子的未来　　132
第10章　未来　　133
我本人对P/NP问题得到解决的前景持悲观态度：我认为 ，而且此生都看不到它的证明。
10.1 　并行计算　　133
10.2 　处理大数据　　135
10.3 　一切事物的网络化　　136
10.4 　应对科技变革　　137
10.5 　关于P/NP问题的结束语　　138
章节注释和文献　　140
人名表　　147
· · · · · · (收起)

一个糖果厂老板决定推出一个活动，将五张金券藏到巧克力的包装里，而这种巧克力每年的产量数以千万计。找到金券的人将得到一次珍贵的参观工厂的机会。 如何找到这些金券？你可以买尽可能多的巧克力。你可能会试试用磁铁，可惜金没有磁性。或者你可以雇用数千人，让他们每人筛查一小堆巧克力。这听起来很傻，但是小姑娘维露卡•索尔特就要这么做，因为她特别想得到一张金券，去参观威利...

• 第一章： 金券