具体描述
P/NP 问题是计算机科学乃至整个数学领域最重要的开放问题。本书从非技术角度介绍了什么是P/NP 问题、它丰富的历史，以及对于人机交互乃至更多问题的数学意义。在这本趣味十足的书中，作者首先追溯了P/NP 问题是如何产生的，然后给出了这个问题的许多实例，涉及经济学、物理学和生物学在内的多个学科。接下来探讨了涵盖P/NP 难题中所有难度等级的问题，从寻找游玩迪士尼乐园所有景点的最短路线，到地图填色问题，再到找出Facebook 上互为好友的一群人。本书深入探寻了计算能够做到什么、无法做到什么，描绘了尝试解决P/NP问题的益处和其中难以预想的挑战。
本书读来引人入胜，适合所有对计算和数学感兴趣的读者。
作者简介
Lance Fortnow
世界级计算机科学家，佐治亚理工学院计算机科学系教授、系主任，在计算复杂性和交互式证明系统领域取得了一系列重要研究成果，为计算机界所熟知。Fortnow早年师从著名的理论计算机科学家Michael Sipser，获麻省理工学院应用数学博士学位。毕业后曾在西北大学、芝加哥大学担任教授，之前还做过NEC研究院高级研究员。他是知名博客Computational Complexity的创办者，经常与他人共同执笔撰写计算复杂性方面的文章。
目录信息
维露卡的父亲索尔特先生是个富商，他决定买光他能找到的巧克力。这还不够，就算有堆积如山的巧克力，要从中找到小小的金券也很困难。
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
1852年，南非数学家弗朗西斯?格思里在为英国各郡的地图填色时，猜想是否只用四种颜色，就足够让所有地图上每两个接壤的地区有不同的颜色。
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
图灵在1936年就指出，图灵机并不是什么都能计算。最著名的例子是停机问题，即没有计算机能通过查看一段代码就知道自己是会永远执行下去还是会最终停止。
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
2010年8月6日，惠普实验室的科学家维纳里?德奥拉利卡向22位顶尖的理论计算机科学家发送了他写的论文，题目简洁有力：“ ”。
7.1 骗子悖论 95
7.2 电路 97
7.3 证明 时常犯的错误 102
7.4 现状 104
第8章 秘密 106
每个人都有秘密，从密码到电子邮件，我们都有不想让别人看到的东西。 意味着某些NP问题拥有不为人知的秘密，无法很快找到它的答案。
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
我本人对P/NP问题得到解决的前景持悲观态度：我认为 ，而且此生都看不到它的证明。
10.1 并行计算 133
10.2 处理大数据 135
10.3 一切事物的网络化 136
10.4 应对科技变革 137
10.5 关于P/NP问题的结束语 138
章节注释和文献 140
人名表 147
· · · · · · (收起)
读后感
我在研究生时，一次一位教授发起了PvsNP问题的讨论，无意中找到了这本书。 这本书是这个问题的科普版，好比霍金的时间简史，对于这个问题，我可以做一个简单介绍： 计算机学中的PvsNP问题好比物理学中的量子力学，甚至更为重要，解决了这个问题就获得了宇宙的最终真理。那时，...
评分我在研究生时，一次一位教授发起了PvsNP问题的讨论，无意中找到了这本书。 这本书是这个问题的科普版，好比霍金的时间简史，对于这个问题，我可以做一个简单介绍： 计算机学中的PvsNP问题好比物理学中的量子力学，甚至更为重要，解决了这个问题就获得了宇宙的最终真理。那时，...
评分我在研究生时，一次一位教授发起了PvsNP问题的讨论，无意中找到了这本书。 这本书是这个问题的科普版，好比霍金的时间简史，对于这个问题，我可以做一个简单介绍： 计算机学中的PvsNP问题好比物理学中的量子力学，甚至更为重要，解决了这个问题就获得了宇宙的最终真理。那时，...
评分如作者所言，写的是一本向公众解释计算机复杂度理论的书。为此，绕开专业的定义和公式，用一个个生动的例子和故事讲解P/NP问题。涉及了P/NP问题的方方面面，对于这样一本薄薄的册子自然无法太过深入，但是相信读者读过对此问题会有一个宏观的认识。 作者已经做得很好。这本书...
评分如作者所言，写的是一本向公众解释计算机复杂度理论的书。为此，绕开专业的定义和公式，用一个个生动的例子和故事讲解P/NP问题。涉及了P/NP问题的方方面面，对于这样一本薄薄的册子自然无法太过深入，但是相信读者读过对此问题会有一个宏观的认识。 作者已经做得很好。这本书...
用户评价
这本《可能与不可能的边界》，从书名本身散发出的那种引人入胜的魅力，就足够让我产生无限的遐想。我是一个喜欢挑战常规思维的人，总觉得我们被太多的“应该”和“不应该”所束缚，被固有的认知模式所限制。这本书的标题，恰好点中了我的痛点，也激发了我内心深处的那股渴望。我猜想，这本书绝非泛泛而谈的理论堆砌，而更可能是一种充满生命力的探索。或许，它会通过一系列生动的故事、鲜活的人物，来展现那些突破界限的瞬间。想象一下，一个在常人看来绝无可能实现的科学实验，最终因为某个天才的奇思妙想而成功；或者，一个在社会压力下被认定为“不可能”的梦想，却被一个执着而勇敢的灵魂，一步步地变成了现实。这样的叙事，总能点燃我内心的激情，让我相信，人类的潜能是无穷的，而所谓的“不可能”，往往只是暂时的障碍。它可能会教会我，如何识别那些真正无法逾越的鸿沟，又如何去拥抱那些看似遥不可及的可能性。
评分这本书的封面上，那个简约而富有张力的标题——《可能与不可能的边界》——就足以勾起我强烈的好奇心。我常常会在书店里，漫无目的地翻阅，寻找那种能瞬间抓住我的灵魂的文字。这一次，它恰好出现在了我眼前。封面的设计，低调却不失深邃，仿佛暗示着书中蕴藏着某种超越日常的哲思。我脑海中浮现出无数的可能性：它或许是一部关于科学突破的史诗，讲述人类如何一步步挑战认知的极限，将那些曾经的“不可能”变为现实；又或许，它是一本探讨哲学思辨的巨著，引导读者深入反思我们对现实世界的理解，审视那些我们习以为常的“可能”与“不可能”的界限，究竟是由什么决定的。是逻辑？是情感？还是我们根深蒂固的认知框架？我无法确定，但正是这种未知，这种期待，让我迫不及待地想要打开它，去探寻那些隐藏在标题背后的答案。它可能会让我重新审视自己的人生选择，那些曾经因为“不可能”而放弃的梦想，是否真的遥不可及？或者，它会揭示出，我们所谓的“不可能”，不过是想象力的囚笼。
评分当我在书架上看到《可能与不可能的边界》这个书名时，一股奇妙的共鸣油然而生。我一直认为，人类的进步，很大程度上就是不断模糊和拓展“可能”与“不可能”之间界限的过程。这本书，听起来就像是对这个过程的一次深刻剖析。我猜测，它可能不是一本简单的科普读物，也不是一本纯粹的哲学论文，而是一种更加融合、更加贴近生活的探讨。也许，它会从我们日常生活中遇到的各种“不可能”出发，比如“我不可能减肥成功”、“我不可能找到那份理想的工作”、“我不可能改变现状”等等，然后层层剥茧，揭示出这些“不可能”背后的心理、社会，甚至生理上的制约。更重要的是，它可能还会提供破局之道。它会告诉我，如何识别那些真正无法逾越的物理定律，又如何去突破那些仅仅存在于我们思维中的“不可能”的藩篱。我期待着，它能给予我力量，让我不再被那些虚幻的“不可能”所吓倒，而是勇敢地去尝试，去创造属于自己的“可能”。
评分《可能与不可能的边界》，光是这个名字，就足以让我产生一种莫名的敬畏感。它似乎预示着一场思维的冒险，一次对既定现实的温柔颠覆。我尤其期待它能在我们对“不可能”的定义上，提供全新的视角。我们常常因为“不可能”而止步，因为“不可能”而放弃，但这本书，会不会挑战我们这个根深蒂固的认知？它或许会告诉我们，许多我们认为的“不可能”，只是因为我们尚未找到正确的方法，或者，只是因为我们缺乏足够坚定的信念。我设想，书中可能会穿插一些历史上的案例，那些曾经被斥为疯子的预言，最终却成为了事实；那些被认为荒诞不经的设想，却最终改变了世界。这样的例子，总是极具启发性。它让我相信，每一次看似不可能的突破，都源于一次对边界的试探，一次对固有的框架的挑战。这本书，或许就是一本关于如何识别、跨越、甚至重塑这些边界的指南，它会鼓励我去探索那些我从未敢想过的领域，去拥抱那些我曾因“不可能”而畏惧的挑战。
评分《可能与不可能的边界》，这个书名本身就自带一种诗意和哲思，让我忍不住想要一探究竟。我常常思考，我们所谓的“可能”与“不可能”，究竟是由什么决定的？是客观规律？还是我们主观的认知？这本书，听起来就像是为解决这些疑问而生。我期待着，它能提供一种全新的视角，让我们重新审视自己所处的现实世界。它或许会通过一些引人入胜的故事，来展现那些突破界限的伟大成就，比如人类首次登月，或者基因编辑技术的诞生。但同时，它也可能深入探讨那些隐藏在“不可能”背后的原因，是认知局限？是社会偏见？还是个人内心的恐惧？我希望这本书能够引导我去思考，如何才能更好地理解和把握“可能”与“不可能”的微妙关系，如何在有限的条件下，最大化地创造“可能”，而又不被那些虚幻的“不可能”所束缚。它可能会是一本关于勇气、智慧和创造力的指南，帮助我在人生的旅途中，更加清晰地认识和挑战那些看似不可逾越的界限。
评分高中生看的
评分没有想象中的深入，作者说他想写一本关于计算理论的《时间简史》，从这个角度说作者做到了。对于想比较深入了解，会有点失望，100来页的书少了点内容
评分14.9.3-非常奇趣。
评分这么一本小薄书卖39真是……………………扣1星
评分即使以人邮出版的标准看定价也太高。不过内容还不错，高中到非专业研究生读读都会有启发。有人吐槽书名翻译，个人感觉那个副标题“P/NP问题趣史”很贴切，这本书并不是要告诉你P/NP的严格定义和经典证明尝试，说白了是一些有启发的“八卦”。另外有人说翻译不行，我也并未感到阅读不适。除了量子力学那一章原文解释得比较简洁外，其他部分翻译和原文比都尽可能做到了准确，而且我也能完全理解，不存在什么佶屈聱牙造成门槛的术语。第二章假想P=NP的未来，以及中段人们试图证明P/NP的尝试及误区都很有趣。作者点到为止，更专业的可能要去直接爬paper吧……
