作者：Lance Fortnow
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
可能与不可能的边界：PNP问题趣史试读：
前言
近半数的美国人都拥有智能手机。智能手机也是计算机，其计算能力比几十年前的超级计算机还要强。计算机将世界上的信息呈现在我们眼前，也帮我们梳理信息。计算机让人们可以彼此交流，无论什么身份，地处何方。计算机能执行数量巨大的运算，从模拟宇宙事件到调度复杂的航线。计算机可以识别人的声音、面孔和动作。计算机可以获悉人们的喜好，并据此推荐图书、音乐和电影。在不远的将来，借助计算机技术，无人驾驶的汽车将随处可见。这么说，计算机简直无所不能。
真是这样吗？在这本书里，我们将探讨许多计算问题，其中一部分可能永远都无法用简单的计算得到答案。试着解答它们是计算机科学，乃至整个数学和科学领域最重要的挑战。人们给这些问题起了一个有些奇怪的名字：P/NP问题。
P/NP是克雷数学研究所公布的7个千禧年数学难题之一，该研究所为求解这道难题设立了百万美元的奖金。不过，P/NP问题的意义远不止于此。
P指的是用计算机能很快求解的问题，NP指的是我们想找到最优解的问题。如果P=NP，那么我们将很容易找到任意给定问题的解。P=NP意味着我们所了解的社会将发生巨变，医学、科学、娱乐和人类社会一切任务的自动化程度都将立即发生质的飞跃。
相反，如果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进发吧！兰斯·福特诺于伊利诺伊州埃文斯顿致谢
首先感谢Moshe Vardi，是他鼓励我写作，他也是我发表在《ACM通讯》杂志上的“P/NP问题的现状”一文的编辑。这篇文章受欢迎的程度让我萌发了把它扩展成一本科普书的念头。
跟我一块写博客的Bill Gasarch不断鼓励我，并仔细审阅了全书各章的初稿。Alana Lidawer和John、Jim，以及Chris Purtilo也阅读了全书的初稿，并提出了许多宝贵意见。KuanLing Chen、Josh Grochow、Ralph Hansen、Adam Kalinich、David Pennock和Rahul Santhanam分别对本书的部分章节提出了许多宝贵的意见。
Manuel Blum、Steve Cook、David Johnson、Leonid Levin和Albert Meyer分别以其个人独到的视角向我讲述了P/NP问题的早期历史。Alexander Razborov对俄罗斯历史的介绍对我帮助很大。
这本书的写作离不开我的生活圈子。作为计算机科学家，我在工作和生活中会与其他研究人员、学生，以及数不清的人交流，这种交流也让我受益匪浅。在此特别感谢加州大学伯克利分校、麻省理工学院、芝加哥大学、阿姆斯特丹的数学与计算机科学中心、NEC研究院、丰田工业大学芝加哥分校以及西北大学的同行们，与他们真挚而友好的讨论让我获益良多。
另外，我还要特别感谢两个人，他们对我早年P/NP问题观念的形成影响很大：Juris Hartmanis，我在康奈尔大学读本科期间首次从他这里接触到了P和NP，还有Michael Sipser，他是我在加州大学伯克利分校和麻省理工学院的博士学位指导老师和好朋友。
在为第6章的地图填色问题寻找例子时，我在网上寻求了帮助，感谢那些做出回应的人：Chris Bogart、HsienChih Chang、Pálvölgyi Dömötör、David Eppstein、Lukasz Grabowski、Gil Kalai、Charles Martel以及Derrick Stolee。
写作期间，我在西北大学的Robert R. McCormick工程与应用科学学院担任电子工程和计算机科学教授。西北大学十分鼓励向公众传播知识的著书活动。我充分利用了教职的特权，尤其是利用了学校图书馆丰富的资源，包括纸质文献和电子文献。西北大学的教职工是最棒的，我的行政助理Marjorie Reyes对我帮助同样很大。
普林斯顿大学出版社的编辑Vickie Kearn为我提供了悉心的指导，并在著书的各个阶段仔细审阅了手稿，让这本书变得更好。我还想感谢Vickie的助手Quinn Fusting，以及出版社的全体工作人员。
最大的感谢留给我的家人：妻子Marcy、两个女儿Annie和Molly，感谢她们对我的爱与鼓励。第1章金券
一个糖果厂老板决定推出一个活动，将五张金券藏到巧克力的包装里，而这种巧克力每年的产量数以千万计。找到金券的人将得到一次珍贵的参观工厂的机会。
如何找到这些金券？你可以买尽可能多的巧克力。你可能会试试用磁铁，可惜金没有磁性。或者你可以雇用数千人，让他们每人筛查一小堆巧克力。这听起来很傻，但是小姑娘维露卡·索尔特就要这么做，因为她特别想得到一张金券，去参观威利·旺卡的巧克力工厂。
维露卡的父亲索尔特先生是个富商，他决定买光他能找到的巧克力。这还不够，就算有堆积如山的巧克力，要从中找到小小的金券也很困难。索尔特先生也有一家工厂，他不惜动用工厂的工人，终于找到了一张金券。他对记者讲述了找到金券的过程：我是做花生生意的，知道吧，我有大约100个女工为我剥花生，然后将它们做成烤花生米和腌花生米。她们整天就坐在那儿剥花生。所以我跟她们说：“好了姑娘们，不要剥花生了，大家开始给我剥这些破糖纸吧！”然后她们就剥。我让工厂的每一个工人都铆足了劲地撕掉巧克力的包装纸，从早干到晚。但是三天过去了，我们还是没走运。哦，那可真够呛！我可怜的小维露卡越来越暴躁，每次我一回家她就朝我嚷嚷：“我的金券在哪儿？我要我的金券！”她撒泼又打滚儿，踢腿又叫喊，实在招人烦。我可不希望看到我的小宝贝这么不高兴，所以我决定一直找，不找到她要的东西誓不罢休。终于，在第四天的晚上，一个女工大叫：“我找到金券了！”然后我说：“把它给我，快！”她给了我，然后我跑着回家把它交给了亲爱的维露卡，她高兴得合不拢嘴。我们家又变得其乐融融了。
和索尔特先生一样，无论你打算怎么找那张金券，你都需要大量时间、金钱，或者运气。也许有一天，有人能发明出一个快速找到金券的便宜装置，也许这样的装置并不存在。
然而，1000万对于今天的计算机来说只是很小的数字。如果你把糖果数字化，录入一个数据库，现在的电脑只用不到一秒就能把它找一遍。虽然计算机比人快得多，但它面对的问题的规模也比在糖果里找金券大得多。
现在最大的电子数据集合规模有多大？比如，整个互联网，考虑到所有视频、音频、电子邮件及其他一切，总的信息量差不多有1 000 000 000 000 000 000字节，最多相差几个0。一个字节大致对应键盘上的一个字符。这个数很大，但记住，计算机也很快。一般的笔记本电脑每秒可以执行1万亿次操作，这样算来，理论上只需要不到4个月就能搜完整个互联网的内容，前提是你能把整个互联网装到你电脑的内存里。Google每时每刻都在搜索整个互联网，它使用了几十万台快速的计算机。
如果计算机可以很快地搜遍整个互联网，看起来好像我们就解决了这个找金券问题的电子版。但是，计算机不仅要帮人们搜索已有的数据，还要搜索问题的所有可能解。
认识一下可怜的旅行推销员Mary，她来自华盛顿特区，为美国木槌集团公司工作。她需要从家乡旅行到48个州的首府，向各州法院推销木槌。木槌公司为了削减成本，让Mary找到通过所有城市的最短路径。Mary画了一张图，写写画画了一会儿，制订了一个不错的路线。图1-1 旅行推销员问题的地图1 1英里约合1.609千米。——编者注
差旅部门的人想让Mary试试能否找到另一条路线，把路程缩短到11 000英里以下。Mary写了个计算机程序，试图穷举所有可能的路线，找出最短的一条，但是一周以后，程序还没跑完。Mary坐下来开始算数。作为第一站的城市有48种选择，然后从剩下的47个城市中选一个作为第二站，再从剩下的46个城市中选一个，以此类推。可能的路径共有48×47×46×…×2×1种，也就是下面这个62位数：
12 413 915 592 536 072 670 862 289 047 373 375 038 521 486 354 677 760 000 000 000
即使计算机计算一条路线的时间等于光通过最小的原子直径的时间（大约0.000 000 000 000 000 000 33秒），仍然需要十亿亿亿倍于宇宙年龄的时间才能算完。难怪Mary的电脑算了一周还没有完。Mary想知道有没有比穷举更好的方法找到最佳路线，就像在所有可能行程的“巧克力山”里面刨出那张小小的金券。
这就是本书最基本的问题：P/NP问题。其中的一个实例就是能否为旅行推销员找到最短路径。P和NP自有其十分专业的定义，但是把它们看做概念比看做数学对象更好。NP是存在解的问题的集合，P则是能很快找到解的问题的集合。P=NP意味着我们能总是很快地计算出任何问题的解，当然也包括找到旅行推销员的最短路径。相反，P≠NP意味着我们不能。1.1 划分的难题
看下边38个数字：
14 175, 15 055, 16 616, 17 495, 18 072, 19 390, 19 731, 22 161, 23 320, 23 717, 26 343, 28 725, 29 127, 32 257, 40 020, 41 867, 43 155, 46 298, 56 734, 57 176, 58 306, 61 848, 65 825, 66 042, 68 634, 69 189, 72 936, 74 287, 74 537, 81 942, 82 027, 82 623, 82 802, 82 988, 90 467, 97 042, 97 507, 99 564
这38个数字之和为2 000 000。你能把它们平分成两组，每组19个数字之和分别为1 000 000吗？你可以使用计算器、电子表格或写一个计算机程序。（答案在本章最后。）
不那么简单，是吧？把这些数分成两组有170亿种方式。如果程序编得巧妙，使用当今较快的计算机能够找到一个解。但如果给你3800个数，或者3800万个数呢？短小的计算机程序可没法给出答案了！
这只是个无意义的数学谜题吗？就算存在一个厉害的计算机程序，它能解决这个平分数组的问题（假设有解），那又如何呢？如果是这样的话，我们能用这个程序做更多的事。这个程序能解决所有的问题，包括旅行推销员问题。这个简短的难题抓住了P/NP问题的本质：一个程序如果能解决这个难题的复杂版本，那么它也能解出任意问题。1.2 手
你的手是最不可思议的工程装置，它能戳、抓和指，能系鞋带，能射箭，还能弹钢琴、拉小提琴，能变戏法，能驾驶车、船、火车或飞机。你的手可以握住其他人的手，或跟他们玩拇指相扑。手可以比划出信号语言，也能通过写字或打字来交流。手可以轻抚，也能重击。手可以使用修理钟表的精密工具，也能操作链条锯。有才华的人的双手可以创造艺术杰作，写出音乐或诗歌。人类取得的几乎所有成就，都离不开双手。
一只手有27块骨头，5根手指，包括最重要的拇指。手具有结构复杂的神经、肌腱和肌肉，这些都包裹在富有弹性的皮肤里。然而，这一不可思议的装置，自然造物的杰作，却不能自己做事，而只能执行人脑的指令。死人的手平平无奇，做不了任何事情。
手就是自然的硬件，硬件本身不能做什么。手需要软件（也就是大脑指令）来控制，软件告诉它如何执行和实现大脑希望它做的事情。
松冈容子是华盛顿大学的机器人学教授，她带领科研小组制作了一个解剖学上正确无误的机械手，其手指有和人类手指同样的动作自由度。理论上她的机械手可以完成人手能做的任何事情，但实际上，它只能完成很简单的任务，因为写一个计算机程序来全方位控制松冈的机械手，是非常困难的。在协调多块肌肉的运动时，即使是完成最简单的任务，也需要很复杂的代码。
然而我们的脑就能控制手。可以将脑看做一个性能强大的计算机，如果脑能控制手去系鞋带或是创作艺术，那么计算机程序也一定能。
知道这样的程序存在并不意味着就能找到它们。随着时间的推移，计算机科学家肯定会写出更精深的程序，松冈的机械手将能执行更复杂的活动。这肯定是一个精彩的旅程，但也可能进展缓慢、举步维艰。
一定要这样缓慢吗？想象一下，只要我们简单描述一项任务，马上就会有一个程序提供相应的功能；给计算机输入一段演示人如何打结的电影，然后它立刻就能用机械手重复打结的过程；把莎士比亚全集录入计算机，然后它就能创作一部新的“莎士比亚”戏剧；只要我们能认出某个东西，就能找到它。这些梦想都能成真——前提是P=NP。
P/NP问题的魅力就在这里。究竟能否让所有的事都变得易如反掌？还是说，有些事情注定就没有简单的解决方法？不能排除这种可能性。无论如何，我们并不指望生活会那么简单。尽管我们并不认为P=NP，但这么美好的世界却让我们忍不住充满憧憬。1.3 P/NP问题
P/NP问题讨论的是以上所述的所有问题，以及许多与之类似的问题。它们归根到底都是在问：我们搜索大量可能性的速度能有多快？我们找到“金券”（即最佳答案）的过程能变得多容易？
P/NP问题是库尔特·哥德尔在1956年寄给约翰·冯·诺依曼的一封信中首次提出的，哥德尔和冯·诺依曼都是20世纪数学界的泰斗。这封信后来不幸遗失，20世纪80年代又被找到。P/NP问题在学术界的亮相是在20世纪70年代初，由斯蒂芬·库克和列昂尼德·莱文独立提出，当时两位所在的国家正在冷战。之后理查德·卡普列出了这个领域中的21个重要难题，包括前面提到的旅行推销员难题和划分难题。计算机科学家从卡普的工作开始认识到P/NP问题极为重要，由此计算机科学研究的方向发生了戏剧性的转变。如今，P/NP问题的关键性作用已经不仅限于计算机科学领域，还延伸到其他许多领域，如生物学、医学、经济学和物理学。
P/NP问题已成为所有数学领域最难的开放问题之一。1994年安德鲁·怀尔斯证明了费马大定理，受这一消息的鼓舞，克雷数学研究所决定举办竞赛，攻克他们认为最为重要而尚未解决的数学难题。2000年，他们列出了下面这7个千禧年难题，并为每道难题的攻破设立了100万美元的奖金。1. 贝赫和斯维讷通-戴尔猜想（Birch and Swinnerton-Dyer
conjecture）2. 霍奇猜想（Hodge conjecture）3. 纳维-斯托克斯方程（Navier-Stokes equations）4. P/NP问题（P versus NP）5. 庞加莱猜想（Poincaré conjecture）6. 黎曼猜想（Riemann hypothesis）7. 杨-米尔斯理论（Yang-Mills theory）
千禧年难题中的庞加莱猜想已于2003年被格里高利·佩雷尔曼解决，但他拒绝了100万美元的奖金。截至本书写作时其他6个难题都尚未解决。
解决P/NP问题就能拿到100万美元，这可是货真价实的金券啊！
更妙的是，如果你能证明P=NP，那么你也就掌握了找到金券的秘诀，解决其余的千禧年难题将是举手之劳。也就是说，证明了P=NP，你就能解决6道千禧年难题，并得到600万美元。然而证明P=NP或P≠NP可没那么容易。一心想得到600万美元的人最好去玩彩票，那样把握更大一些。1.4 找到金券
有时候我们能够找到金券。比如我在芝加哥，想开车去纽约，往车载GPS里输入地址，一两分钟之内它就能给出一条从芝加哥到纽约的最快路线，然后我就可以踏上旅程了。几百万字节的内存便可容纳全部的美国街道地图，但地图中可能的路线远远超过几百万。从芝加哥到纽约所有可能的行车路线有多少条？不开错方向的情况下，保守计算可得出的路线数目大到了“不可思议”，即1后边跟63个0。GPS根本没有时间检查所有的可能性，但还是能找到最快的路线。
旅行时间有一个有趣的性质。随便选一个中间地点（比如匹兹堡），从芝加哥经过匹兹堡到纽约的最短路线，一定是芝加哥到匹兹堡的最短路线，再接上匹兹堡到纽约的最短路线。不走匹兹堡可能有更快的路线，但是芝加哥到纽约的最短路线，绝不会比从芝加哥经过匹兹堡到纽约的最短路线还要长。
GPS的计算机程序正是利用了这个性质，快速缩小搜索范围并找到了最佳路线。这可能仍需要检查上亿条路线，但是GPS的计算机处理器完全能胜任，毕竟这个数字比“不可思议”小多了。
找到最短路径并没有体现P/NP问题的全部力量。最短路径问题告诉我们，全部的可能性数量特别大，但这并不总意味着必须遍历所有的可能性才能找到答案。P/NP问题其实是问，是不是对于任意给定的搜索问题，我们都不必遍历所有的可能性就能找到答案？1.5 漫漫长途
本书讲的是P和NP的故事。什么是P和NP？P/NP描述的是哪类问题？所有搜索问题中最难的问题——“NP完全问题”是怎么回事？这些问题如何影响P/NP问题？
举个简单的例子，Facebook上的好友圈子（即团，clique）中，最大的包含多少人？100人，还是1000人？即使你拥有Facebook的全部数据，这个问题也很难求解。求解较大规模团问题的困难程度，不亚于任何搜索问题。
如果P=NP会怎么样？那么我们将迎来一个美好的世界，计算所有的事物都将易如反掌。我们能快速地了解一切，揭开世界上所有事物的神秘面纱，从治愈绝症到洞悉宇宙的本质。美好的世界也有它灰暗的一面，人们将丧失隐私、丢掉工作，因为没有什么是计算机不能知道或完成的。
这样美好的世界几乎不太可能。困难的搜索问题仍将存在，我们想要甚至需要找到它们的答案。其实我们大可不必放弃。计算机科学家已研发出许多技术，包括很有可能对许多问题奏效的启发式方法，以及能给出接近理想解的近似技术。
P和NP问题是如何产生的？这个故事发生在世界因冷战被割裂的那段日子，其实可以把它分成两个故事来讲。有关高性能计算的思路和问题分别在两个世界独立发展，而这两个世界的研究最终殊途同归，从而产生了P/NP问题。
从哪里着手证明P≠NP？库尔特·哥德尔证明数学不能解决所有的问题。能否用类似的方法，证明存在不能快速解决的搜索问题？为了分析问题的复杂度，我们可以把计算过程分解为最基本的单元。算术几何学（数学的一个抽象分支），为人们能在有朝一日解决这个重要的问题带来了新的希望。但我们距离那一天还很远。
P≠NP会带来什么好处呢？它能帮助我们保守秘密，产生看上去真随机的伪随机数。
未来基于量子力学的计算机能否让P/NP问题变得无足轻重？不太可能，不过量子计算机的建成将解决一部分现在计算机束手无策的问题，比如大数的因数分解。此外，量子力学也会透露P是否等于NP的玄机。
未来将会如何呢？我们仍将面临计算领域的巨大挑战。人们如何与互相协作处理问题的计算机打交道？如何分析每天产生的海量数据？所有事物都能联网，世界将会怎样？要解决这些问题，P/NP问题只会变得更为关键。1.6 划分难题的解
以下38个数
14 175, 15 055, 16 616, 17 495, 18 072, 19 390, 19 731, 22 161, 23 320, 23 717, 26 343, 28 725, 29 127, 32 257, 40 020, 41 867, 43 155, 46 298, 56 734, 57 176, 58 306, 61 848, 65 825, 66 042, 68 634, 69 189, 72 936, 74 287, 74 537, 81 942, 82 027, 82 623, 82 802, 82 988, 90 467, 97 042, 97 507, 99 564
可分成如下两组：
15 055, 16 616, 19 390, 22 161, 26 343, 40 020, 41 867, 43 155, 46 298,57 176, 58 306, 65 825, 66 042, 69 189, 74 537, 81 942, 82 623, 82 988,90 467
和
14 175, 17 495, 18 072, 19 731, 23 320, 23 717, 28 725, 29 127, 32 257, 56 734, 61 848, 68 634, 72 936, 74 287, 82 027, 82 802, 97 042, 97 507, 99 564
每组中所有数字之和都是1 000 000。第2章美妙的世界
假设有人请你写一篇关于过去20年互联网带来的社会变革的论文。你是写装在口袋里的设备让人们能够随时访问所有公开的信息，还是会探讨发生在音乐、电影、出版和新闻产业的巨大变化？无论怎么写，短短一篇论文都很难公允地描述过去20年发生的变化。好了，再想象一下：如果是让你在这些变化尚未发生的20世纪90年代写这篇论文，你又会对未来做出怎样的预测？
如果P=NP被证实，即我们掌握了一种对所有NP问题都有效的快速算法，那么社会将发生更加巨大的变化，互联网看起来只是历史的一个补充说明。不光不可能描述全部的变化，甚至不太可能预测新技术带来的深远影响。
为了能让读者对那个美妙的世界有些许认知，现在让我们来想象一下发现解决NP问题的有效算法几年之后会发生什么。让我们一起跳到2026年，去看看一个P=NP被证实的世界——当然，这个世界是科幻的。首先，咱们来看看这个世界是怎么打造出来的。2.1 厄巴纳算法
2016年，捷克数学家米莱娜·帕维尔用邮件转发了一个她认为理论上能有效解决NP问题的算法。计算机科学和数学界经过仔细验证，一致认为米莱娜所言不虚，算法确实解决了伟大的P/NP问题。米莱娜将算法发表成论文，文章本身的名字很低调，叫做“论一个库克没有解决的问题”（On an Open Problem of Cook），而《纽约时报》介绍文章的标题更为直白，恰如其分地表明了它的价值：“P=NP”。
2018年，米莱娜成为第一个获得数学领域最高荣誉（菲尔兹奖）的女性。一年后克雷数学研究所奖给米莱娜一张价值100万美元的支票。她成为继格里高利·佩雷尔曼之后第二个成功解决千禧年数学难题的人。不像佩雷尔曼，她高兴地收下了奖金，并将其中一部分（数额未知）捐给了故乡布拉格的大学作为奖学金。
虽然米莱娜的算法在理论上是一个突破，但因为实际执行时间过长而缺乏实用价值。2017年，俄罗斯计算机科学家明斯克·波洛夫采用一种巧妙的方法改良了米莱娜的算法，从而大幅改进了算法的执行效率，然而还是不够实用。
一年后在中国，清华大学的一群本科生仔细优化了明斯克的代码，在当时世界上最快的超级计算机上运行它。他们在几天之内就解决了较大规模的团问题和其他几个常见的NP问题。清华大学开始与波音、戴姆勒-奔驰等工业巨头签约，帮助这些公司解决一些棘手的优化问题。他们帮助波音为新797客机设计出了更好的机翼，使得客机能直接从伦敦飞到悉尼。
史蒂夫·弗兰克是伊利诺伊大学的博士生，此时在清华做一学期的访问学者，他有幸参与了项目的研究工作。回到伊利诺伊州的厄巴纳后，他向导师诉苦，无论他们如何优化，还是要花几天时间才能解决一个中等规模的NP问题。“如果你遇到灯神，它能满足你一个愿望，你会许什么愿？”导师说。“不知道。”史蒂夫回答。“让它给你一个能满足你所有愿望的灯神！”
史蒂夫脑中一亮。他知道一定存在一个能更好解决团问题的算法，而他自己想不出这个算法。但是他遇到了灯神——清华的代码，他可以用很快的速度搜索指数级数量的可能算法。所以他基于清华的例程写了一个搜索更好的NP问题算法的程序。他获准可以使用位于伊利诺伊大学的国家超级计算应用中心（NCSA）的计算资源。经过几周的计算，他的工作初见成效。他找到了一个比清华的算法性能高5%的算法。这一结果发篇论文绰绰有余，但不会产生轰动效应。
他的导师淡淡地说：“用新算法再试一次。”
于是史蒂夫用他的新算法找到了一个更快的解决NP问题的算法。几周后他获得了20%的性能提升。
但他的导师还不满意：“再试一次。”
史蒂夫这样回答：“我为什么不编个程序让计算机自动使用找到的算法来查找更好的算法呢？”
导师的目光变得异样起来，仿佛在说你终于开窍了，又仿佛在说，这么明显的事你怎么现在才想到。
史蒂夫回到办公室，开始写一个算法，让计算机能自动利用搜索到的更快的算法去查找比当前算法更快的算法，这样一直找下去，直到性能无法提升为止。史蒂夫的一个同事问他是否担心天网效应。“天网是啥？”“当计算机变得足够聪明，有了自我意识，它就会接管世界，就像《终结者》系列电影里的超级计算机‘天网’一样。”“不，只是计算机代码而已，不用担心。”
史蒂夫写好了代码，最后一次在NCSA的超级计算机上运行它。随着迭代次数的增加，由计算机自动生成的求解NP问题的算法性能变得越来越好，最后在停止时，生成了一个有4200万行机器码的让人费解的程序。它求解NP问题的速度，那是相当快。（顺便说一句，计算机依然没有自我意识。）某高校出版社将这个算法自豪地称为“厄巴纳算法”，后来这个名字被保留了下来。
伊利诺伊大学的数学家们开始率先使用厄巴纳算法，用它来证明剩下的千禧年数学难题。证明过程是计算机生成的，复杂到人类几乎无法理解。克雷数学研究所很快发表声明，不再接受基于米莱娜·帕维尔发现的百万美元算法衍生出来的任何算法的数学证明。
许多试图以许可证和买断方式获得厄巴纳算法的公司都陷入了诉讼泥潭，因为与算法有关的各方——资助米莱娜研究的捷克政府、史蒂夫·弗兰克、史蒂夫的导师以及NCSA，都主张自己对厄巴纳算法的所有权。
世界贸易组织在认识到该算法的重大意义后，要求公开厄巴纳算法，供全人类共同享用，相关各方将得到合理的补偿，并成立专门委员会落实。2019年10月23日，厄巴纳算法对所有人公开了。
从此，世界发生了一系列戏剧性的变化……2.2 计算机1，癌症0
海伦的医生走进检查室，关上身后的门，说：“我有个坏消息，你患有胰腺癌。”
海伦倒抽一口冷气。她才43岁，家里有三个孩子，最大的15岁，最小的才6岁。“你怎么可能知道，我不过验了个血。”“我们现在只需要得到血液中的标记物和DNA，就可以判断你是否患有癌症，是哪种癌症，以及癌变的程度。如果你坚持，我们可以做活检，但是没必要冒这个险，现有的检查已经足够精确了。”“我的表姐在8年前被诊断出胰腺癌，那会儿是2018年。当时这病没什么治疗措施，几个月后她就过世了。”“幸好医学在过去十年里有了很大的进步。我们意识到适合所有人的抗癌方法疗效有限，人们需要针对个体的治疗方案，就是先鉴别出某个人的正常DNA和癌细胞的突变DNA，然后制造出特定的蛋白质，其折叠方式不仅能有效地饿死癌细胞，而且对正常细胞没有任何影响。死亡的癌细胞会被排出体外。”“听起来会很贵。”海伦评论道。“化疗才贵呢，这种疗法的成本只有几千美元，将来还会更便宜。大部分费用都可以由你的医疗保险支付。”“太好了！过去十年究竟发生了什么，让检验和治疗变得如此简便？”“这些想法很早就有了，但在过去，即使是世界上最快的计算机在解决DNA密码方面也显得太慢，所以一直没有什么突破。厄巴纳算法的出现改变了这种状况，过去几年里我们取得了难以置信的进步。通常一项新技术出来后，我们会做很多年实验才会投入临床使用，但是这种疗法的初期测试太成功了，以至于FDA觉得不立即批准投入使用都不道德，毕竟有那么多的癌症患者，他们等不起。”“什么时候开始治疗？”海伦问。“开始？我们已经用抽的血做完了分析，这是你的处方。”
医生递给海伦的不是一张纸，而是一个U盘。“这里面有治疗你的癌症的蛋白质的编码信息。把它带到药房，让他们为你制作药片。一天一片，连吃两周，你体内的癌细胞就清扫干净了，没有任何副作用。但是要注意，这个处方只对你起作用，其他人的DNA不同，如果吃了你的药片，可能会产生严重的后果，甚至是致命的。”“没有副作用？头发不会掉光？没有恶心想吐的感觉？癌症及早发现的话只要服几片药就好了，跟治感冒一样？所有这一切都得益于一个算法？”“不完全准确，”医生说，“没错，厄巴纳算法帮人们战胜了癌魔，治愈了艾滋病和糖尿病。可是，我们还不知道如何应对普通感冒。”2.3 棒球比赛“真是打棒球的好天气！”兰迪对他12岁的女儿凯特说，这是他第一次带女儿到圣路易斯看棒球比赛。圣路易斯红雀队主场对战密尔沃基酿酒人，这场2026赛季末的夺冠赛扣人心弦。兰迪感叹棒球运动和他小时候相比变化不少。这项运动在科技的使用上曾经是那么地原始，甚至连计时装置都不用，而如今它同样受到了厄巴纳算法的巨大影响。
首先当然是棒球赛程安排上的变化。直到2004年，棒球大联盟（Major League Baseball）的赛程都是由亨利和霍莉·斯蒂芬森夫妇来安排的，这对夫妻档安排赛程的依据是几条简单的规则，例如每个队主场和客场的比赛数最好大致相等，还会照顾某些地方的偏好，如波士顿的球迷希望把波士顿红袜队的一次主场比赛安排在四月中旬爱国者日的白天，因为波士顿马拉松赛的参赛人员会在那天从球场旁边经过。2005年棒球大联盟与匹兹堡的赛事筹划集团（Sports Scheduling Group）签订了合作协议，因为这家公司知道如何避免两支队伍在连续的几周内多次交锋。众所周知，暴雨天气无法进行室外棒球赛，但赛事筹划集团在安排赛事时从不考虑下雨的因素，原因很简单，没办法在开赛前的12月份预测整个赛季的天气状况。当然，那是厄巴纳算法出现之前的事情了。
在算法的帮助下，人类的天气预测技术取得了不可思议的进步，可以提前一年准确预测温度、风力、云量和降水。类似的算法可以做到准确预测风暴、龙卷风和飓风，让人们有充足的准备和撤离时间。新的天气预测技术同样改变了人们的日常生活。学校会对未来下雪的日子提前做准备。承办户外婚礼的教堂会根据未来婚期的天气状况向新人收取不同的费用，想在好天气结婚的要多交钱，愿意在炎热、潮湿或下雨天举行露天婚礼的则可以享受折扣。大多数人都想在好天气看棒球赛，所以如果底特律会下雨或者阴天的话，完全可以把比赛安排到明尼阿波利斯去，那里将艳阳高照。
赛场和电视机前的观众都想看到高质量的比赛，尤其是临近赛季末尾时优秀球队之间的激烈比拼。兰迪小时候，判断哪支球队会赢没有科学的方法，基本靠猜。而新的预测工具料事如神，能提前告诉人们哪些球队将进入9月份的冠军争夺赛。计算机预测胜场也并非完全准确。棒球运动具有随机性，每个赛季的实际战局都会与预测有那么几场的出入。然而算法的模型仍能以极高的准确率预测哪些球队会在赛季末尾名列前茅。那些没被预测为夺冠热门的球队的球迷们每年都会抱怨计算机算错了，然而计算机通常是对的，唯一的一次预测失败，被人们津津乐道。
棒球产业的大亨们想用更好的方式安排比赛，目标之一是让每个人都能在最好的天气看到强队之间的火拼，当然还有更实际的成本控制方面的诉求，比如尽可能缩短每个团队花在路上的总时间。15年前，根本不可能将很多方面纳入考虑，那会使需要检验的计划规模庞大得难以处理。但现在，无论要求多么苛刻，厄巴纳算法都能在几分钟内给出一个最棒的赛程表。
所以兰迪才能在这样完美的天气带凯特去看这样一场关键的棒球赛。虽然这天红雀队的观赛费用比平时高，但兰迪很乐意为此买单。
兰迪和凯特进入看台的时候没有检票员和检票闸机，他们就直接走进了体育场，监控摄像头通过人脸识别软件认出了他们，通过数据匹配证实他们已经买过票了。如果有人企图不买票就进场，保安肯定会找出他，人们很早就知道了这一事实，不敢冒险去挑战识别软件的威力了。
兰迪和女儿就座后，兰迪四处打量，发现偌大的球场空空荡荡，看不到几年前巨大的电视摄像机和操作员了。取代这些的是围绕在球场周围的20台小得几乎看不见的摄影机。20台摄像机的画面输入计算机后，软件利用厄巴纳算法构建出比赛的实时三维渲染数据。从这些渲染数据中，计算机可以合成从任意角度拍摄球场任意地点的视频短片。观众能从捕手的视角观看比赛，也能从跑垒员的视角观看他滑向三垒的英姿。虽然这些画面其实是计算机合成的，但看起来非常逼真。在一次有名的实验中，请100个观众观看并排放在一起的两个短片，其中一个短片是实际拍摄的，另一个是计算机合成的。结果89人都误以为计算机合成的短片是实际拍摄的。
新型电视允许人们直接下载三维渲染数据，然后控制虚拟的摄像机飞到赛场上的任意位置，随心所欲地享受比赛过程。
计算机在球棒击球的那一瞬间，准确预测出球的飞行轨迹，然后立即选一个最佳的观看角度，把比赛实时呈现出来。运营电视网络转播的只有四个人：两个评论员，一个制片人，还有一个技术员（处理偶发的故障）。评论员说的是英语，而由于圣路易斯和密尔沃基两队分别有一个知名的日本球员，这场比赛在东京也很受关注，那里的观众听到的将是日语的评论。实际上日本观众听到的是美国的评论员在说话，但是计算机立即用语音识别、翻译和语音合成工具模拟出地道的日语。这些工具自然也使用了厄巴纳算法。这场比赛在全世界用876种语言和方言播出。
转播一场比赛用四个人似乎已经很少了，但在电视网络的副总裁看来，最好一个人都不用。几年以来，大学校园都通过布置在球场周围的摄像机记录练习赛，供教练们进行战术分析。最近，一个具有创业精神的学生成功地将厄巴纳算法应用到这些录像数据上，制作出全套的转播视频，其中评论、特写视角、数据统计样样俱全，一切完全由计算机自动生成。很快所有大学（以及许多高中比赛和小型联赛）的每种运动赛事都可以在互联网上实时观看，还拥有各种语言的版本。这些转播的质量也许比不上真人做评论的那些节目，但也差不到哪里去。
幻想比赛达到了前所未有的高度。计算机可以生成体育迷们梦想中看到的比赛，不仅可以让不在一支球队的球星们并肩作战，甚至还可以关公战秦琼，让活跃在不同时代的球星同场竞技：让全盛时期的传奇投手赛·杨对战如日中天的乔·狄马乔，或是1927年的洋基队对战1998年的洋基队。幻想与现实变得难以区分。某个愚人节，ESPN电视台的一个计算机程序员改写了部分代码，让电视机前的观众看到他所喜爱的波士顿凯尔特人队打败了纽约尼克斯队，而现实比赛中，尼克斯才是真正的胜者。这次转播事故让许多人丢了饭碗。
计算机充当裁判也表现完美，它总能精准无误地判别坏球、好球、出局和全垒打。为了削减成本，小型联赛和大学里的所有比赛都用计算机来做裁判。而大型联赛坚持使用真人裁判，每当错误的判决改变比赛的局势都会遭到一片质疑之声。
由于担心计算机做管理工作也比人类经理更为出色（这种担心是正确的），棒球大联盟在经历过2022年世界巡回赛的失败之后，宣布禁止球队使用计算机设备。负责人称：“这是为了棒球运动好。”
兰迪一边喝着啤酒一边啃着汉堡（饮料和食物变得更好吃了，因为厄巴纳算法改进了配方），一边还欣赏着比赛。比赛进行的方式和他小的时候相比没有什么变化。他其实完全可以省下大笔钱，在家里欣赏从完美视角呈现的比赛三维实况转播。尽管科技让在家看球的体验远比在体育场看球还要好，兰迪还是愿意享受一种参与感，厄巴纳算法再厉害也无法再现这种感情上的依恋。
计算机可以自动生成计分表，但兰迪还是教女儿凯特怎样在纸上计分，就像他父亲教他的那样。纵使以厄巴纳算法为代表的科技改变了几乎所有的事物，但比赛还是那个比赛。三振出局的老规矩，永远都不会改变。2.4 奥卡姆剃刀
为何形式简单的计算机代码，只要强大到厄巴纳算法那种级别，就能带给我们一个理想的世界，让人们可以治愈疾病、预测天气，以及创造几乎能够以假乱真的虚拟环境？为了回答这个问题，我们需要回到14世纪的早期。
奥卡姆的威廉还是一名青年时就加入了英国的方济各会。和许多14世纪的宗教团体一样，方济各会的总部设在牛津，它为牛津大学的在校生提供了住所。威廉是一名主修神学的牛津学生，尽管没有毕业，他后来还是成了中世纪最主要的思想家之一，对物理学、神学、逻辑学和哲学都作出了巨大贡献。他最著名的思想是奥卡姆剃刀法则，即主张最简单的解释通常是最好的解释。“剃刀”一词比喻我们可以把一个理论中纠缠复杂的部分像胡子一样“剃除”，只留下最简单的解释。这一思想贯穿文艺复兴时代一直延续到今天，引领着一代又一代人的科学和哲学思潮。
17世纪法国哲学家勒内·笛卡儿通晓奥卡姆剃刀法则。他怀疑一切，甚至对周围世界的存在性提出质疑。笛卡儿最为著名的哲学命题是Cogito ergo sum，即“我思故我在”。在他的著作《方法论》中，笛卡尔摒弃了一切前提假设，仅从他能通过思考意识到自己这一点，得出了“笛卡尔是存在的”这一结论。那么笛卡尔如何解释他感受到的复杂世界呢？万物是否有可能只存在于笛卡尔的意识中？笛卡儿不赞同这种想法，因为有另一种更简单和更合理的解释，那就是其他人和他一样，大家共同生活在一个可以认知和理解的物质世界之中。我被“我思故我在”这几个字迷住了，我确信它是真理，证据只有一条，那就是我清楚地看到，存在是一个事物能够思辨的必要前提。我甚至可以论断，一般地讲，一切我们能清晰明确地在脑中显现的事物都是真实的。然而值得注意的问题是，很难恰当地分辨哪些物体是我们能够明确地想象的。笛卡儿，《方法论》，第四部分
和笛卡儿同时代的约翰内斯·开普勒通过观测行星运动，归纳出了一系列描述它们运动路线和速度的定律。至于为什么行星运动符合这些定律，开普勒无法给出一个简单的解释。
艾萨克·牛顿将奥卡姆剃刀法则运用到物理世界。他著名的运动定律以非常简单的方式，表述了物体如何相互作用：1. 如果不给物体施加任何力，静止的物体会保持静止，运动的物体
速度保持不变；2. 施加于物体上的力将产生一个与其大小成正比的固定加速度；3. 一个物体给另一个物体施加力，则施力物体也会受到来自受力物
体的大小相等、方向相反的力。
通过把运动定律和他对引力的简单描述相结合，牛顿展示了如何从天体的运动推导出开普勒定律。简单的表述可以具有强大的解释能力。
几个世纪后，阿尔伯特·爱因斯坦和其他科学家从理论上提出：对于运动速度接近光速的物体，牛顿的简单运动定律是不成立的。后来的一些实验基本证明爱因斯坦是对的。他的名言是：“把所有事都变得尽可能简单，而不可过于简单。”这并不意味着牛顿错了，恰恰相反，他的模型是对我们所认知的世界的一个很好的近似。甚至在今天，对于包括驾驶汽车，以及高中大部分科学实验在内的一些简单场合，牛顿定律仍然非常适用。
对于非常小的粒子，甚至爱因斯坦的理论也不再成立，它们所服从的法则被称为量子力学。当代物理学家试图找到一种能融合爱因斯坦的广义相对论和量子力学的理论，即所谓的“大统一理论”。
简单的模型永远无法反映世界全部的复杂性，但它们通常可以很接近这个目标。为某些情形找到一种简单的解释，就能对未来发生的类似情形做出很好的预测。近年来我们看到这个原理在计算机科学世界得到了充分的体现。
今天我可以手写一张支票，用手机拍张支票的照片，然后通过互联网存入支票。银行的软件通过照片就能识别交易金额和账号，即使支票是手写的也没关系。如果没有疑议，银行职员甚至都不用亲自去看这张支票。
识别位于支票底部的账号比较容易，组成账号的数字符合固定的格式，这是特意为方便计算机识别而设计的。
但是支票上的金额是手写的“30美元”。每个人写字的方式都不一样，计算机如何能判别这张支票的金额呢？图2-1 支票
这个问题不简单。不信你看数字2有多少种写法。图2-2 各种手写的数字2
计算机科学的一个分支——机器学习就是处理这类问题的。首先用大量的数据训练一个算法，在这个例子里，数据就是人们写数字2和其他数字的样例。算法会建立一个相对简单的模型，然后尝试用这个模型正确区分各种手写的数字。训练得好的算法能对新的数字进行正确的分类，即使是对训练期之后写出的数字也不例外。
过去20年，计算机科学家在机器学习领域取得了长足的进步，研究出了通过检查几千到几百万样例，计算出将数据分类的正确方式。除了识别支票之外，许多照片处理程序还可以根据人脸来对照片排序，效果还过得去。Amazon、Netflix和Pandora等公司能为顾客推荐图书、电影和音乐，根据的是顾客之前购买过的商品，以及观影和听歌的模式。语音识别和语言翻译虽然不能做到和真人一样，但会让你大致了解写的或说的是什么。垃圾邮件识别工具屏蔽了人们不想要的几乎所有信息。到2020年，所有的汽车有望能够自动驾驶。
这类技术所能做到的差不多就是这些了，未来取得的进步最终将越变越小。这是否意味着奥卡姆剃刀不再锋利，宝刀已老？
倒也未必。奥卡姆剃刀法则说的是最简单的解释问题的方法就是最好的方法，但它并没有告诉你如何找到那个最简表述。如今的机器学习技术只能使用简单的数据表述方式，通常会把数据的多种特征用相对直接的方式加以合并。如何找到最简表述，即找到任意形式的程序中最短小而有效的数据分类程序，是一个困难的问题，一个NP问题。
如果能使用快速解决所有NP问题的厄巴纳算法，找到最简单的数据分类程序就变成了一道简单的编程练习。我们需要做的只是把海量数据交给算法，然后看着它完成剩下的工作。这样一来，我们几乎能了解所有的事物。
我们已经看到了厄巴纳算法帮助人类治愈了很多疾病，并且改变了美国的棒球运动。接下来让我们回到未来，看看它是如何改变艺术的。2.5 创造力的自动化
借助奥卡姆剃刀，厄巴纳算法几乎能让我们了解一切，包括艺术作品为何优秀，音乐为何流行，言语为何动人心魄。要知道P=NP意味着只要能评测一个事物，我们就能找到它。所以只要有一个慧眼识珠的算法，再用厄巴纳算法就能很快找到这颗“明珠”。
2022年，美国民主党总统候选人初选即将在科罗拉多州开始。之前的两周，皮特·约翰逊得票第三，远远落后于前两名。情况在“那次演讲”后改变了。在韦尔市的一个小剧场里，约翰逊进行了一次短短10分钟的演讲，甚至没有媒体列席。然而这次有关科罗拉多和美国的演讲格外动人心魄，在场的32个人起立报以热烈的掌声。
一个与会者用手机录下了演讲，发到了网上。几百万人在线观看了演讲，后来甚至有几千人言之凿凿，说自己亲临了那次演讲。约翰逊赢得了初选，成为2024年总统竞选的热门候选人。为进一步提高自己的曝光率，皮特·约翰逊炒了自己的竞选经理，然后换了一个享誉全国的专家。
被炒的前竞选经理忿忿不平，召开记者会爆料了那次演讲背后的真相。当时情况不妙，如果不马上使出一些厉害手段，皮特·约翰逊的竞选之旅眼看就要到头了。于是，竞选经理雇了一个计算机程序员，程序员先下载了数以万计的近几十年来广受欢迎的演讲，然后用厄巴纳算法生成了一个关于科罗拉多及国内外局势的优秀演讲稿。皮特·约翰逊经过多次排练，把计算机生成的稿子背得滚瓜烂熟，然后才有了韦尔市的演讲。竞选经理请观众把此次记者会的录像也传到网上。
舆论一片哗然。有些人表示愤慨，另一些则认为政客们的演讲稿是由职业撰稿人捉刀还是由计算机生成没多大差别。皮特·约翰逊失掉了民心，也失掉了大选。到2026年的时候，几乎所有候选人撰写演讲稿时都会让计算机帮忙甚至代劳，大家习以为常，见怪不怪。当然，人人演讲出色，等于没人演讲出色。
古典音乐家用厄巴纳算法完成大师们未完成的名作，如普契尼的歌剧《图兰朵》、马勒的《第十交响曲》、舒伯特的《第八交响曲》（又名《未完成交响曲》）；而且还能再续经典，如创作出贝多芬的第十部交响曲。由算法生成的最著名的交响曲叫做《厄巴纳第一交响曲》，古典乐迷非常喜爱它。有人甚至用厄巴纳算法制作出甲壳虫和猫王的新专辑，将已故歌星们的嗓音模仿得惟妙惟肖。音乐评论界的专家对这些“作品”嗤之以鼻，认为它们只是照猫画虎，缺乏真正的创意，但还是有很多人下载。
还有人用计算机生成新的画作、小说、戏剧和诗歌。一个电影爱好者最近制作了一部由盛年的亨弗莱·鲍嘉和茱莉娅·罗伯茨主演的爱情喜剧片，看起来就好像两人真的穿越了时光，在片场大飙感情戏一样。想看由导演蒂姆·伯顿执镜的《绿野仙踪》？没问题！
Amazon能做的超越了原来的图书推荐。你只要花一张电影票的钱，就可以让Amazon写一部完全符合你口味的小说。NBC电视台目前推出了一档“现场直播”的动作冒险剧集，完全由计算机创作，不需要任何编剧和演员。最新的Xbox上的电子游戏带给你沉浸式的叙事和世界体验。故事的发展不再是线性的，而是有着无限的可能性，玩家完全按自由意志行动，并为自己的行为承担相应的后果。不少人觉得难以区分游戏和现实生活，比较明显的区别是现实生活可能没有游戏那么刺激。
这些新的娱乐选择让世人目眩神迷，为之痴狂。许多文章都在批判真实表达的缺失。究竟厄巴纳算法标志着一个艺术新纪元的诞生，还是人类创造力的死亡，这在未来的几个世纪仍是一个争议不断的话题。2.6 终极侦探
司法机关觉得厄巴纳算法在侦破犯罪案件方面堪称鬼才，它在追捕嫌犯时总是能完成不可能完成的任务。然而也有一些争议。
后厄巴纳算法时代的亚特兰大出现了一起多人死亡的凶杀案，警方从犯罪现场的快餐包装纸上收集到了一份DNA，但在美国DNA联合索引系统（CODIS）中找不到与之匹配的数据。佐治亚理工学院的一个计算机科学家用厄巴纳算法和CODIS创建了一个新的程序，该程序不仅可以利用这些DNA数据预测嫌犯的身高、眼睛和皮肤颜色等外貌特征，还能预测嫌犯的个性特点以及可能从事的行业。然后这个计算机科学家带领学生，把CODIS中的DNA数据和这些人的面部照片匹配，从而研发出一种技术，根据某人的DNA生成相貌的大致素描，前提是知道目标的年龄和面部毛发类型。
于是警方想用这个算法找到和犯罪现场DNA匹配的罪犯头像照片，但没有成功。他们又把算法运行在驾驶执照的头像数据库里，这回找到了一个嫌疑人——乔治·布朗，几小时后把他抓了进来。乔治·布朗没有不在场的证明，而且是唯一符合由DNA生成的相貌素描的人，但除此之外，没有发现他与此次犯罪有明显关联。他拒绝提供DNA样本，警方得到了法院的搜查令，然后比对了他和犯罪现场留下的DNA，果然相符。乔治·布朗被认定有罪，判处死刑。
布朗提出上诉，他的律师说根据犯罪现场留下的DNA画出素描的行为侵犯了乔治·布朗的隐私权。美国最高法院裁定，使用DNA判定一个人的身份是合法的。警方只是将算法运行在合法取得的证据上。
然而，此案引发了公众对丧失隐私权的大规模抗议。38个州决定DNA只能用来匹配合法收录到CODIS中的嫌犯，除此之外不能使用。最后，佐治亚州州长将乔治·布朗的死刑改判为终身监禁。2.7 美妙世界的阴暗面
以前人们依靠公钥加密技术，可以不经过初始化设置就安全地通过网络将信用卡号传给交易公司。而厄巴纳算法能在瞬间破解公钥加密。起初，电子商务的发展经历了一些挫折，但互联网巨头们很快就联合起来，将业务迁移到使用私钥加密的系统。很快一个私钥注册处被建立起来，人们从街边的药店就能买到一个密钥U盘，里面装着几十亿个一次性的私钥。虽然比原来稍显不便，但是电子商务活动又兴旺起来。
更多人感到个人隐私被剥夺，并对此感到恐慌。原来看起来人畜无害的视频摄像头突然能识别和追踪每个人了。更恐怖的是，计算机算法能准确预测你走哪条路，听什么歌，看什么电影，买什么产品，简直比你自己还了解你。定向投放的广告很容易就能诱导你改变消费习惯。被认为可能是窃贼或恐怖分子的人会立刻被系统认出来，受到严密的监视。
对厄巴纳算法最大的顾虑是就业问题。从秘书到中层管理人员，几乎所有的白领职位都受到算法的威胁，它可以理解各种信息（甚至包括不太正式的电子邮件、音频和视频），生成信件和报表，还能根据分析得出结论和制定决策。那些原来需要外包的工作都交给计算机算法做就行了，这被称为“厄巴纳包”。工作人员如果不能让雇主相信自己提供的附加价值，就会失业。大公司继续理直气壮地削减薪资。不少公司撤销了设在海外的人工咨询台服务，代之以计算机化的支持多种语言和方言的应答系统。许多消费者在民意测验中表示计算机提供的服务比被取代的人工服务更加有用。
有些国家开始立法限制厄巴纳算法的应用以保护就业岗位，但在来自其他国家的商业竞争压力面前，这些法律很快就被废止了。情况逐渐有了一些转好的迹象。厄巴纳算法刺激了疲软的经济，催生了新兴产业的雏形。大学里开设了新的课程，如“厄巴纳优化”，讲授拿到一个问题后如何以最快捷简便的方式运用厄巴纳算法解决它。虽然长远来看，算法创造的就业机将会远远多于失去的就业机会，但还是有许多人对算法耿耿于怀，替那些无法适应新经济体制的失业者鸣不平。
政府继续推行法令，保护民众不受厄巴纳算法的冲击，但科技的影响覆水难收。人类总是能很快适应新形势，渐渐很少有人会在民意测验中表示愿意时光倒流，回到古老的2012年，逃离这个算法带来的美妙世界。
试读结束[说明：试读内容隐藏了图片]