《可能与不可能的边界:P/NP问题趣史》(美)LanceFortnow电子书图书酷

本站主要采用城通网盘链接分享，因为其他网盘会和谐链接！非VIP会员的朋友请点击普通下载，弹窗关闭即可。速度可能比较慢，请耐心等待，提高下载速度，送您10元消费红包。

内容简介

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

/序言

　　近半数的美国人都拥有智能手机。智能手机也是计算机，其计算能力比几十年前的超级计算机还要强。计算机将世界上的信息呈现在我们眼前，也帮我们梳理信息。计算机让人们可以彼此交流，无论什么身份，地处何方。计算机能执行数量巨大的运算，从模拟宇宙事件到调度复杂的航线。计算机可以识别人的声音、面孔和动作。计算机可以获悉人们的喜好，并据以推荐图书、音乐和电影。在不远的将来，借助计算机技术，无人驾驶的汽车将随处可见。这么说，计算机简直无所不能。
真是这样吗？在这本书里，我们将探讨许多计算问题，其中一部分可能永远都无法用简单的计算得到答案。试着解答它们是计算机科学，乃至整个数学和科学领域最重要的挑战。人们给这些问题起了一个有些奇怪的名字：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进发吧！
兰斯·福特诺
于伊利诺伊州埃文斯顿

作者简介

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