可能与不可能的边界:P/NP问题趣史 [平装] 9787115335661

P/NP 问题是计算机科学乃至整个数学领域最重要的开放问题。本书从非技术角度介绍了什么是P/NP 问题、它丰富的历史，以及对于人机交互乃至更多问题的数学意义。在这本趣味十足的书中，作者首先追溯了P/NP 问题是如何产生的，然后给出了这个问题的许多实例，涉及经济学、物理学和生物学在内的多个学科。接下来探讨了涵盖P/NP 难题中所有难度等级的问题，从寻找游玩迪士尼乐园所有景点的最短路线，到地图填色问题，再到找出Facebook 上互为好友的一群人。本书深入探寻了计算能够做到什么、无法做到什么，描绘了尝试解决P/NP问题的益处和其中难以预想的挑战。 本书读来引人入胜，适合所有对计算和数学感兴趣的读者。众多世界级计算机科学家联袂推荐； 《出版人周刊》、《科学》等杂志好评如潮； 像《时间简史》一样风趣幽默的P/NP问题阐释； 关于计算、数学与逻辑的一场盛宴。 “我敢打赌你会爱上这本书。它通俗易懂，把一个顶尖数学问题演绎得跌宕起伏，读者时而充满期待、为之感到兴奋，时而又黯然神伤。读罢此书，我有几分期待P不等于NP了。” ——Vint Cerf，Google副总裁、首席互联网布道师、互联网之父 “P/NP问题是计算机科学乃至整个数学的基础。本书对该问题的阐释令人着迷，既追溯了其历史，也探讨了其现状与影响。行文过程中涉及许多大学计算机科学的研究主题，语言风趣幽默，读者不需要有多么高深的数学知识，只要会解数独游戏即可畅读。我强烈推荐。” ——Stephen Cook，P/NP问题的构造者 “Fortnow是一位世界级计算机科学专家，他通过本书详述了该领域最负盛名和意义最为重大的一个未解难题。作者向普通大众深入浅出地讲解了计算复杂性这个看似神秘的领域，对于‘什么是可计算的，能算得多快’这类问题感兴趣的读者可以一饱眼福。” ——John MacCormick，《改变未来的九大算法》作者 “对于P/NP问题的重要性，Fortnow作了最好的诠释。” ——William J. Cook，《迷茫的旅行商：一个无处不在的计算机算法问题》作者 “本书巨细靡遗，对于P/NP这个历久弥新的重大话题，作者详尽追溯了其发展历史和学术背景。即使是复杂性理论学家也能从本书获益，而向普罗大众介绍复杂性理论，本书可谓开山之作！” ——William Gasarch，马里兰大学教授 专业书评： “Fortnow真正做到了引人入胜，读者沉迷于P/NP问题的神秘与重要性之中难以自拔。” ——《出版人周刊》 “Fortnow的著作是一张入场券，它把我们这个时代面临的最难的理论问题降到一般民众的认知水平来演绎，甚至连民选官员都看得懂。” ——《科学》 “这是一个神秘、艰难、令人沮丧的世界，这是一个探索和发现的世界，这是一个喜悦和意外迟来的世界，这是Fortnow眼中的P/NP世界。” ——《纽约客》 “P/NP问题的定义原本极其专业和刁钻，但Fortnow不仅具有化繁为简的能力，还能虚实结合、融会贯通，将该问题的重要性描述得淋漓尽致。” ——《新科学人》 读者评论： “我敢打赌你会爱上这本书。它通俗易懂，把一个顶尖数学问题演绎得跌宕起伏，读者时而充满期待、为之感到兴奋，时而又黯然神伤。读罢此书，我有几分期待P不等于NP了。” ——Vint Cerf，Google副总裁、首席互联网布道师、互联网之父 “P/NP问题是计算机科学乃至整个数学的基础。本书对该问题的阐释令人着迷，既追溯了其历史，也探讨了其现状与影响。行文过程中涉及许多大学计算机科学的研究主题，语言风趣幽默，读者不需要有多么高深的数学知识，只要会解数独游戏即可畅读。我强烈推荐。” ——Stephen Cook，P/NP问题的构造者 “Fortnow是一位世界级计算机科学专家，他通过本书详述了该领域最负盛名和意义最为重大的一个未解难题。作者向普通大众深入浅出地讲解了计算复杂性这个看似神秘的领域，对于‘什么是可计算的，能算得多快’这类问题感兴趣的读者可以一饱眼福。” ——John MacCormick，《改变未来的九大算法》作者 “对于P/NP问题的重要性，Fortnow作了最好的诠释。” ——William J. Cook，《迷茫的旅行商：一个无处不在的计算机算法问题》作者 “本书巨细靡遗，对于P/NP这个历久弥新的重大话题，作者详尽追溯了其发展历史和学术背景。即使是复杂性理论学家也能从本书获益，而向普罗大众介绍复杂性理论，本书可谓开山之作！” ——William Gasarch，马里兰大学教授 Lance Fortnow 世界级计算机科学家，佐治亚理工学院计算机科学系教授、系主任，在计算复杂性和交互式证明系统领域取得了一系列重要研究成果，为计算机界所熟知。Fortnow早年师从著名的理论计算机科学家Michael Sipser，获麻省理工学院应用数学博士学位。毕业后曾在西北大学、芝加哥大学担任教授，之前还做过NEC研究院高级研究员。他是知名博客Computational Complexity的创办者，经常与他人共同执笔撰写计算复杂性方面的文章。 第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 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 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 7.1 骗子悖论 95 7.2 电路 97 7.3 证明时常犯的错误 102 7.4 现状 104 第8章 秘密 106 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 10.1 并行计算 133 10.2 处理大数据 135 10.3 一切事物的网络化 136 10.4 应对科技变革 137 10.5 关于P/NP问题的结束语 138 章节注释和文献 140 人名表 147 【前言】 近半数的美国人都拥有智能手机。智能手机也是计算机，其计算能力比几十年前的超级计算机还要强。计算机将世界上的信息呈现在我们眼前，也帮我们梳理信息。计算机让人们可以彼此交流，无论什么身份，地处何方。计算机能执行数量巨大的运算，从模拟宇宙事件到调度复杂的航线。计算机可以识别人的声音、面孔和动作。计算机可以获悉人们的喜好，并据以推荐图书、音乐和电影。在不远的将来，借助计算机技术，无人驾驶的汽车将随处可见。这么说，计算机简直无所不能。 真是这样吗？在这本书里，我们将探讨许多计算问题，其中一部分可能永远都无法用简单的计算得到答案。试着解答它们是计算机科学，乃至整个数学和科学领域最重要的挑战。人们给这些问题起了一个有些奇怪的名字：P/NP问题。 P/NP是克雷数学研究所公布的7个千禧年数学难题之一，该研究所为求解这道难题设立了百万美元的奖金。不过，P/NP问题的意义远不止于此。 P指的是用计算机能很快求解的问题，NP指的是我们想找到最优解的问题。如果 ，那么我们将很容易找到任意给定问题的解。 意味着我们所了解的社会将发生剧变，医学、科学、娱乐和人类社会一切任务的自动化程度都将立即发生质的飞跃。 相反，如果 ，那么总会有部分问题无法迅速地被解决。那也没有关系，因为我们可以根据具体情况研发出某些技术来解决这些问题。 意味着不可能用自动化的方法解决所有问题。然而，知道哪些工具不好用也有助于人们找到更好用的工具。 2008年8月，《ACM通讯》的主编莫舍?瓦迪约我写一篇关于P/NP问题的文章。ACM（美国计算机协会）是一个为计算机研究学者和从业人员服务的重要社团，《ACM通讯》则是该协会刊登文章的主要杂志。 一开始我想把写稿的事推给另一位计算机科学家，但后来我还是答应了。当时莫舍是这么劝说我的：“如果那帮物理学家可以写关于弦理论的畅销文章（和图书），那我们也可以向公众解释计算复杂度理论目前的进展，我希望如此。”于是我写了一篇文章，该文章以《ACM通讯》的读者为主要受众，不仅介绍了P/NP问题的现状（基本可以概括为“悬而未决”），也讲了一些人们在处理困难问题时积累的技巧。“P/NP问题的现状”（The Status of the P versus NP Problem）发表在2009年9月的《ACM通讯》上，它很快就成为该刊物创刊以来下载次数最多的文章。 关于P/NP问题，我觉得还有很多故事可讲，而那篇文章的大受欢迎，似乎表明是时候面向更广的受众（而不仅是科学家们）来讲述这些故事了。 我将那篇短文作为本书的框架结构，将原来文章的各个部分扩展为现在的章节。我还受到了史蒂芬?霍金的《时间简史》的启发：该书尽量绕开晦涩的公式和术语，采用生动的例子和故事来解释物理。我试图以同样的方式来讲解P/NP问题，借此探讨P/NP问题的本质和重要意义。 本书没有给出P/NP问题的正式定义，有很多教科书和网站都详细论述了P和NP的定义及技术结论。本书旨在让你对计算科学的潜能和局限性有更多的了解，这非常有好处，毕竟计算机如今已成为人类生活不可或缺的部分了。 向P和NP进发吧！ 兰斯?福特诺 于伊利诺伊州埃文斯顿 版权页： 3.列昂尼德·栗文 1961年，李雅普诺夫从莫斯科国立大学转到新西伯利亚国立大学任教，在那里他建立了理论控制学系。新西伯利亚市距离莫斯科有2800公里之遥，是俄罗斯第三大城市，也是西伯利亚最大的城市。 系里的老师大部分是雅布隆斯基和李雅普诺夫以前的学生，来自莫斯科。新组建的理论控制学系很快成为俄罗斯理论控制学的第二大研究中心。鲍里斯·特拉腾布罗在40岁就已经是这个领域的资深研究者，他在中心建成之时就已加入，并很快成为领军人物。1962年，Y.M.巴兹丁从里加市拉脱维亚大学获得博士学位，并加入了新西伯利亚的研究中心。特拉腾布罗开始和巴兹丁合作，研究计算复杂度的基础理论，许多拉脱维亚和新西伯利亚的学生慕名而来。在20世纪60年代，他们开始建立一个复杂度的算法理论，类似于同时期西方的研究。 但苏联的计算复杂度理论的发展并不顺利，正如特拉腾布罗1984年写的那样：我们与“主流”的控制论研究者们（主要是雅布隆斯基）之间的关系恶化了，对此感到担心。他们对于将算法理论引入复杂度研究领域的态度十分消极……他们不相信计算复杂度和算法复杂度在蛮力搜索领域起到的作用。 这些学术上的分歧很可能因为蛮力搜索上的争议而加深，特别是当雅布隆斯基在那样一个协调和控制数学研究的组织中担任高位之后。 柯尔莫哥洛夫于1963年夏天访问了新西伯利亚，他和特拉腾布罗分享了学术成果，探讨了算法理论如何促进对信息和复杂度的理解。 在那次访问之后，柯尔莫哥洛夫很快到了基辅大学，并访问了一个为数学和物理学神童专设的高中寄宿学校。他随便问了几个问题，很多问题都被一个叫列昂尼德·莱文的15岁孩子解答了。柯尔莫哥洛夫后来邀请莱文到莫斯科大学跟他学习。莱文在研究生期间的杰出工作分为两个方向。 首先，莱文发明了一个通用的搜索算法。假设Alice对Bob说她有能快速求解团问题的算法，但是不告诉Bob是什么算法。