可能与不可能的边界:P/NP问题趣史

副标题：无

作者: Lance Fortnow

内容简介：

​
前言近半数的美国人都拥有智能手机。智能手机也是计算机，其计算能力比几十年前的超级计算机还要强。计算机将世界上的信息呈现在我们眼前，也帮我们梳理信息。计算机让人们可以彼此交流，无论什么身份，地处何方。计算机能执行数量巨大的运算，从模拟宇宙事件到调度复杂的航线。计算机可以识别人的声音、面孔和动作。计算机可以获悉人们的喜好，并据此推荐图书、音乐和电影。在不远的将来，借助计算机技术，无人驾驶的汽车将随处可见。这么说，计算机简直无所不能。

真是这样吗？在这本书里，我们将探讨许多计算问题，其中一部分可能永远都无法用简单的计算得到答案。试着解答它们是计算机科学，乃至整个数学和科学领域最重要的挑战。人们给这些问题起了一个有些奇怪的名字：P/NP问题。

P/NP是克雷数学研究所公布的7个千禧年数学难题之一，该研究所为求解这道难题设立了百万美元的奖金。不过，P/NP问题的意义远不止于此。

P指的是用计算机能很快求解的问题，NP指的是我们想找到最优解的问题。如果P=NP，那么我们将很容易找到任意给定问题的解。P=NP意味着我们所了解的社会将发生巨变，医学、科学、娱乐和人类社会一切任务的自动化程度都将立即发生质的飞跃。

相反，如果P≠NP，那么总会有部分问题无法迅速地被解决。那也没有关系，因为我们可以根据具体情况研发出某些技术来解决这些问题。P≠NP意味着不可能用自动化的方法解决所有问题。然而，知道哪些工具不好用也有助于人们找到更好用的工具。

2008年8月，《ACM通讯》的主编莫舍·瓦迪约我写一篇关于P/NP问题的文章。ACM（美国计算机协会）是一个为计算机研究学者和从业人员服务的重要社团，《ACM通讯》则是该协会刊登文章的主要杂志。

一开始我想把写稿的事推给另一位计算机科学家，但后来我还是答应了。当时莫舍是这么劝说我的：“如果那帮物理学家可以写关于弦理论的畅销文章（和图书），那我

目录预览：

​ 可能与不可能的边界：P/NP问题趣史
版权信息
目录
版权声明
献词
前言
致谢
第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　敌友国之外
3.10　Icosian游戏的一个解
第4章　NP中最难的问题
4.1　第一个NP完全问题
4.2　21个问题
4.3　起个好名字有那么重要吗
4.4　超越卡普的工作
4.5　漏网之鱼
第5章　P和NP诞生前的历史
5.1　西方
5.2　东方
5.3　哥德尔的信
5.4　火星人法则
第6章　处理困难的问题
6.1　蛮力
6.2　启发式方法
6.3　搜索小规模的解
6.4　近似计算方法
6.5　解决一个不同的问题
6.6　接受