本书首先追溯了P/NP问题是如何产生的;然后给出了这个问题的许多实例, 涉及经济学, 物理学和生物学在内的多个学科;接下来探讨了涵盖P/NP难题中所有难度等级的问题, 从寻找游玩迪士尼乐园所有景点的最短路线, 到地图填色等

福特诺 (Fortnow, Lance)

(美)福特诺著;杨帆译

The People's Posts and Telecommunications Publishing House

China, People's Republic, China

Bei jing, 2014

Bookmarks: p1 (p1): 第1章 金券
p1-1 (p3): 1.1 划分的难题
p1-2 (p4): 1.2 手
p1-3 (p5): 1.3 PNP问题
p1-4 (p6): 1.4 找到金券
p1-5 (p7): 1.5 漫漫长途
p1-6 (p8): 1.6 划分难题的解
p2 (p10): 第2章 美妙的世界
p2-1 (p10): 2.1 厄巴纳算法
p2-2 (p13): 2.2 计算机1，癌症0
p2-3 (p14): 2.3 棒球比赛
p2-4 (p17): 2.4 奥卡姆剃刀
p2-5 (p21): 2.5 创造力的自动化
p2-6 (p22): 2.6 终极侦探
p2-7 (p23): 2.7 美妙世界的阴暗面
p2-8 (p24): 2.8 回到现实
p3 (p25): 第3章 P和NP
p3-1 (p25): 3.1 敌友国
p3-2 (p25): 3.2 六度理论
p3-3 (p28): 3.3 牵线搭桥
p3-4 (p31): 3.4 团问题
p3-5 (p32): 3.5 “递棍儿”
p3-6 (p36): 3.6 刷房子
p3-7 (p38): 3.7 分组
p3-8 (p39): 3.8 P和NP
p3-9 (p40): 3.9 敌友国之外
p3-10 (p43): 3.1 0 Icosian游戏的一个解
p4 (p44): 第4章 NP中最难的问题
p4-1 (p44): 4.1 第一个NP完全问题
p4-2 (p47): 4.2 21个问题
p4-3 (p49): 4.3 起个好名字有那么重要吗
p4-4 (p51): 4.4 超越卡普的工作
p4-5 (p57): 4.5 漏网之鱼
p5 (p62): 第5章 P和NP诞生前的历史
p5-1 (p63): 5.1 西方
p5-2 (p68): 5.2 东方
p5-3 (p74): 5.3 哥德尔的信
p5-4 (p74): 5.4 火星人法则
p6 (p76): 第6章 处理困难的问题
p6-1 (p77): 6.1 蛮力
p6-2 (p78): 6.2 启发式方法
p6-3 (p83): 6.3 搜索小规模的解
p6-4 (p85): 6.4 近似计算方法
p6-5 (p90): 6.5 解决一个不同的问题
p6-6 (p92): 6.6 接受现实
p6-7 (p92): 6.7 总结
p7 (p94): 第7章 证明P≠NP
p7-1 (p95): 7.1 骗子悖论
p7-2 (p97): 7.2 电路
p7-3 (p102): 7.3 证明P≠NP时常犯的错误
p7-4 (p104): 7.4 现状
p8 (p106): 第8章 秘密
p8-1 (p106): 8.1 经典密码学简史
p8-2 (p108): 8.2 现代密码学
p8-3 (p111): 8.3 P=NP下的密码学
p8-4 (p112): 8.4 零知识数独
p8-5 (p117): 8.5 玩游戏
p8-6 (p119): 8.6 在云上进行加密计算
p8-7 (p120): 8.7 创造随机性
p8-8 (p121): 8.8 持续的挑战
p9 (p123): 第9章 量子
p9-1 (p123): 9.1 量子录像机
p9-2 (p127): 9.2 量子密码学
p9-3 (p128): 9.3 量子隐形传输
p9-4 (p132): 9.4 量子的未来
p10 (p133): 第10章 未来
p10-1 (p133): 10.1 并行计算
p10-2 (p135): 10.2 处理大数据
p10-3 (p136): 10.3 一切事物的网络化
p10-4 (p137): 10.4 应对科技变革
p10-5 (p138): 10.5 关于P/NP问题的结束语
p11 (p140): 章节注释和文献
p12 (p147): 人名表

2023-10-14