可能与不可能的边界：P/NP问题趣史
12推荐 收藏
22.1K阅读

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

Lance Fortnow (作者) 杨帆 (译者)
暂时缺货 算法 p/np问题 计算复杂度
P/NP问题是计算机科学乃至整个数学领域最重要的开放问题。本书从非技术角度介绍了什么是P/NP问题、它丰富的历史，以及对于人机交互乃至更多问题的数学意义。在这本趣味十足的书中，作者首先追溯了P/NP问题是如何产生的，然后给出了这个问题的许多实例，涉及经济学、物理学和生物学在内的多个学科。接下来探讨了涵盖P/NP难题中所有难度等级的问题，从寻找游玩迪士尼乐园所有景点的最短路线，到地图填色问题，再到找出Facebook上互为好友的一群人。本书深入探寻了计算能够做到什么、无法做到什么，描绘了尝试解决P/NP问题的益处和其中难以预想的挑战。

本书读来引人入胜，适合所有对计算和数学感兴趣的读者。
电子书
￥24.99
格式
mobi   pdf
购买电子书
纸质书
￥30.81 ￥39.00
暂无样书

其他购买方式？

出版信息

本书特色

编辑推荐

1. Vint Cerf等众多世界级计算机科学家联袂推荐；
2. 《出版人周刊》、《科学》等杂志好评如潮；
3. 像《时间简史》一样风趣幽默的P/NP问题阐释；
4. 关于计算、数学与逻辑的一场盛宴。


媒体评论

“Fortnow真正做到了引人入胜，读者沉迷于P/NP问题的神秘与重要性之中难以自拔。” ——《出版人周刊》

“Fortnow的著作是一张入场券，它把我们这个时代面临的最难的理论问题降到一般民众的认知水平来演绎，甚至连民选官员都看得懂。” ——《科学》

“这是一个神秘、艰难、令人沮丧的世界，这是一个探索和发现的世界，这是一个喜悦和意外迟来的世界，这是Fortnow眼中的P/NP世界。” ——《纽约客》

“P/NP问题的定义原本极其专业和刁钻，但Fortnow不仅具有化繁为简的能力，还能虚实结合、融会贯通，将该问题的重要性描述得淋漓尽致。” ——《新科学人》

专业书评

“我敢打赌你会爱上这本书。它通俗易懂，把一个顶尖数学问题演绎得跌宕起伏，读者时而充满期待、为之感到兴奋，时而又黯然神伤。读罢此书，我有几分期待P不等于NP了。” ——Vint Cerf，Google副总裁、首席互联网布道师、互联网之父

“P/NP问题是计算机科学乃至整个数学的基础。本书对该问题的阐释令人着迷，既追溯了其历史，也探讨了其现状与影响。行文过程中涉及许多大学计算机科学的研究主题，语言风趣幽默，读者不需要有多么高深的数学知识，只要会解数独游戏即可畅读。我强烈推荐。” ——Stephen Cook，P/NP问题的构造者

“本书作者是一位世界级计算机科学专家，他通过本书详述了该领域最负盛名和意义最为重大的一个未解难题。作者向普通大众深入浅出地讲解了计算复杂性这个看似神秘的领域，对于‘什么是可计算的，能算得多快’这类问题感兴趣的读者可以一饱眼福。” ——John MacCormick，《改变未来的九大算法》作者 “对于P/NP问题的重要性，Fortnow作了最好的诠释。” ——William J. Cook，《迷茫的旅行商：一个无处不在的计算机算法问题》作者

“本书巨细靡遗，对于P/NP这个历久弥新的重大话题，作者详尽追溯了其发展历史和学术背景。即使是复杂性理论学家也能从本书获益，而向普罗大众介绍复杂性理论，本书可谓开山之作！” ——William Gasarch，马里兰大学教授

目录

版权声明 阅读
献词 阅读
前言 阅读
致谢 阅读
第1章　金券 阅读
第2章　美妙的世界
第3章　P和NP
第4章　NP中最难的问题 阅读
第5章　P和NP诞生前的历史
第6章　处理困难的问题
第7章　证明P≠NP
第8章　秘密
第9章　量子
第10章　未来
章节注释和文献
人名表

作者介绍

Lance Fortnow（作者）世界级计算机科学家，佐治亚理工学院计算机科学系教授、系主任，以在计算复杂性和交互式证明系统领域取得的重要研究成果为计算机界所熟知。Fortnow创立了Computational Complexity博客，并与他人共同执笔撰写计算复杂性相关文章。Fortnow早年师从著名的理论计算机科学家Michael Sipser，获麻省理工学院应用数学专业博士学位。毕业后曾在西北大学、芝加哥大学担任教授，之前还做过NEC研究院高级研究员。

杨帆（译者）软件工程师、技术发烧友、模范消费者。关注动态语言、云计算、数据可视化、产品设计等领域。

相关文章

  • 盼盼姐 4推荐

    世界级计算机科学家Lance Fortnow访谈问题有奖征集

    Lance Fortnow是一位世界级计算机科学家，佐治亚理工学院计算机科学系教授、主席。他的研究关注计算复杂性及其在经济理论上的应用。他在交互式证明系统领域取得的重要研究成果使他获选美国计算机协会院士。Fortnow早年师从著名的理论计算机科学家Michael Sipser，…...

    盼盼姐 发表于 2014-03-19
  • 盼盼姐 8推荐

    世界级计算机科学家Lance Fortnow：教授是世界上最好的职业（图灵访谈）

    Lance Fortnow是一位世界级计算机科学家，佐治亚理工学院计算机科学系教授、主席。他的研究关注计算复杂性及其在经济理论上的应用。他在交互式证明系统领域取得的重要研究成果使他获选美国计算机协会院士。Fortnow教授创立了Computational Complexity博…...

    盼盼姐 发表于 2014-04-01
  • 李松峰 3推荐

    编辑与正则二：把逗号替换为空格

    示例来源：http://www.ituring.com.cn/article/41070 问题描述 有下面这个62位的数，需要把其中的逗号替换成半角空格： 12,4139,1559,2536,0726,7086,2289,0473,7337,5038,5214,8635…...

    李松峰 发表于 2015-05-14
  • 李松峰 5推荐

    编辑与正则四：为大数添加千分位空格

    示例来源：http://www.ituring.com.cn/article/edit/41070 问题描述 有一个很长的大数： 1279834847944074100465236334 要求加上表示千分位的空格。 解决方案 用下面这个查找模式： (\d{1,…...

    李松峰 发表于 2015-05-18
  • 李松峰 14推荐

    找到巧克力中的金券：P/NP问题的历史与故事

    一个糖果厂老板决定推出一个活动，他将五张金券藏到巧克力的包装里，而这种巧克力每年的产量数以千万计。找到金券的人将得到一次珍贵的参观工厂的机会。 如何得到这些金券？你可以买尽可能多的巧克力。你可能会试试用磁铁，可惜金没有磁性。或者你可以雇佣数千人，让他们每人筛查一小堆巧克力。听…...

    李松峰 发表于 2013-05-31
  • 英子 17推荐

    对面的程序Yuan看过来，看过来，这里的内容很精彩！

    首先，感谢您关注这个俗气的题目，我是故意的，想让大家放松一下！当然不必客气，嘻嘻！ ![enter image description here align="center"][1] 此图片来自Google，只为愉悦你的大脑！ 非常负责任地说，小编介绍…...

    英子 发表于 2013-10-09
  • 英子 16推荐

    怕不怕（P/NP）？技术帖

    寻找金券 一个糖果厂老板决定推出一个活动，将五张金券藏到巧克力的包装里，而这种巧克力每年的产量数以千万计。找到金券的人将得到一次珍贵的参观工厂的机会。如何找到这些金券？你可以买尽可能多的巧克力。你可能会试试用磁铁，可惜金没… ...

    英子 发表于 2013-12-09
  • 紫凤 10推荐

    又一千禧年大奖难题被攻破，下一个向P/NP进发吧！

    继千禧年大奖难题「庞加莱猜想」被攻克后，又一千禧年大奖难题「纳维-斯托克斯存在性与光滑性」可能被攻破，现在若是已经解决了两个，那么是不是代表离解决P/NP问题也不远了呢？ 关于千禧年大奖难题（选自维基百科）： 千禧年大奖难题（Millennium Prize Problem…...

    紫凤 发表于 2014-01-13
  • 白龙
    对这个问题很感兴趣，期待
    白龙  发表于 2013-04-21 03:44:31
    推荐
  • 张宁宁
    第二章好有意思，没仔细看日期，还以为NP问题已经被解决了，吓了一跳，哈哈哈
    张宁宁  发表于 2016-01-15 01:52:46
    推荐

    • 整本书都挺有意思哒~

      英子  发表于 2016-01-15 08:46:23
  • aadilah
    等待折扣
    aadilah  发表于 2013-12-08 13:37:10
    推荐