编辑推荐
计算、数学与逻辑的盛宴，像《时间简史》一样风趣。
内容简介
P/NP问题是计算机科学乃至整个数学领域最重要的开放问题。《可能与不可能的边界：P/NP问题趣史》从非技术角度介绍了什么是P/NP问题、它丰富的历史，以及对于人机交互乃至更多问题的数学意义。在这本趣味十足的书中，作者首先追溯了P/NP问题是如何产生的，然后给出了这个问题的许多实例，涉及经济学、物理学和生物学在内的多个学科。接下来探讨了涵盖P/NP难题中所有难度等级的问题，从寻找游玩迪士尼乐园所有景点的最短路线，到地图填色问题，再到找出Facebook上互为好友的一群人。《可能与不可能的边界：P/NP问题趣史》深入探寻了计算能够做到什么、无法做到什么，描绘了尝试解决P/NP问题的益处和其中难以预想的挑战。
作者简介
作者Lance Fortnow，世界级计算机科学家，佐治亚理工学院计算机科学系教授、系主任，在计算复杂性和交互式证明系统领域取得了一系列重要研究成果，为计算机界所熟知。Fortnow早年师从著名的理论计算机科学家Michael Sipser，获麻省理工学院应用数学博士学位。毕业后曾在西北大学、芝加哥大学担任教授，之前还做过NEC研究院高级研究员。他是知名博客Computational Complexity的创办者，经常与他人共同执笔撰写计算复杂性方面的文章。
章节目录
版权信息
版权声明
献词
前言
致谢
第1章 金券
1.1 划分的难题
1.2 手
1.3 P/NP问题
1.4 找到金券
1.5 漫漫长途
1.6 划分难题的解
第2章 美妙的世界
2.1 厄巴纳算法
2.2 计算机1，癌症0
2.3 棒球比赛
2.4 奥卡姆剃刀
2.5 创造力的自动化
2.6 终极侦探
2.7 美妙世界的阴暗面
2.8 回到现实
第3章 P和NP
3.1 敌友国
3.2 六度理论
3.3 牵线搭桥
3.4 团问题
3.5 “递棍儿”
3.6 刷房子
3.7 分组
3.8 P和NP
3.9 敌友国之外
1. 生物学
2. 物理学
3. 经济学
4. 数学
3.10 Icosian游戏的一个解
第4章 NP中最难的问题
4.1 第一个NP完全问题
4.2 21个问题
4.3 起个好名字有那么重要吗
4.4 超越卡普的工作
1. 支配集（Dominating Set）
2. 三角切分问题 （Partition into Triangles）
3. 大规模数独游戏
4. 肾脏交换
4.5 漏网之鱼
1. 图的同构问题
2. 质数和因数分解
3. 线性规划
第5章 P和NP诞生前的历史
5.1 西方
1.阿兰·图灵
2.计算复杂度
3.P和NP
5.2 东方
1.谢尔盖·雅布隆斯基
2. 安德烈·柯尔莫哥洛夫
3. 列昂尼德·莱文
5.3 哥德尔的信
5.4 火星人法则
第6章 处理困难的问题
6.1 蛮力
6.2 启发式方法
6.3 搜索小规模的解
6.4 近似计算方法
6.5 解决一个不同的问题
6.6 接受现实
6.7 总结
第7章 证明P≠NP
7.1 骗子悖论
7.2 电路
7.3 证明P≠NP时常犯的错误
7.4 现状
第8章 秘密
8.1 经典密码学简史
8.2 现代密码学
8.3 P=NP下的密码学
8.4 零知识数独
8.5 玩游戏
8.6 在云上进行加密计算
8.7 创造随机性
8.8 持续的挑战
第9章 量子
9.1 量子录像机
9.2 量子密码学
9.3 量子隐形传输
9.4 量子的未来
第10章 未来
10.1 并行计算
10.2 处理大数据
10.3 一切事物的网络化
10.4 应对科技变革
10.5 关于P/NP问题的结束语
章节注释和文献
前言
第1章
第2章
第3章
第4章
第5章
第6章
第7章
第8章
第9章
第10章
人名表
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
R
S
T
V
W
Y
Z
05. 轻松撰写功能规格书 - 第一部分： 为什么要写？
可能与不可能的边界：P/NP问题趣史是2014年由人民邮电出版社·图灵出品出版,作者[美]Lance Fortnow。
得书感谢您对《可能与不可能的边界：P/NP问题趣史》关注和支持，如本书内容有不良信息或侵权等情形的，请联系本网站。
