可能与不可能的边界

本书副标题是 P/NP 问题趣史

开篇用金券、手（超级灵活，无法使用计算机模拟）、旅行问题、划分两个数组的事例，给大家一个直观的概念：P 问题容易解决，NP 问题不容易解决。若能证明 P=NP，一切很美好；若不能，带来什么呢？长路漫漫，作者提出了很多问题，期待他能在后面一一解决。

作者假想了一个场景，经过一系列努力（这里面还 YY 了清华大学），人类解决了 P=NP 问题，并写出了能够生成代码解决 NP 问题的程序。有了这个程序，分析 DNA 易如反掌，战胜了癌症等各种现在开起来是绝症、疑难杂症；棒球比赛除了规则，一切都变了，计分、处理画面、安排赛事、训练等等，都可以快速的由计算机辅助完成；计算机程序能够创作小说、音乐、电影、游戏等等；不好的方面也有，比如 RSA 一瞬间就被破解了；人们没有隐私可言；很多很多人都要失业了。回到 2012 年（应该是作者写书的年代），不管怎样，有些问题终将被攻破，P 是否等于 NP 呢？继续前进。

作者又假想了一个二万人组成的国家，来阐述 NP 问题。通过几个小问题告诉人们算法的重要性。P 问题，多项式时间复杂度（也称为算术复杂度）就能解决的问题，是简单问题；NP 问题，不确定性多项式时间，不知道有没有多项式时间复杂度的解，但是给出一个解，可以在多项式时间判断正误。但是遗憾的是，至今没能证明 P=NP，但是不代表没有。P=NP 证明不出来，P!=NP 貌似更难证明，哈哈。

一个计算机科学家提出了 P/NP 问题，获得了图灵奖；一个计算机科学家归纳了 NP 问题，也获得了图灵奖；就连这个名字，也是赫赫有名的高德纳先生取的。

西方的美国人和东方的俄罗斯人，独立地发现了 P/NP 问题，可见其是自然孕育的事物，蕴含在生活之中。

不管 P 是否等于 NP，即使等于，在找到 P 算法之前，我们仍然活在一个 NP 的世界。我们采用蛮力法来解决小规模问题，启发算法、近似算法等找一个可接受的解，亦或者，放弃解决某个问题，开心的玩去吧，因为目前为止，既没有证明 P=NP，也没有证明 P!=NP，且二者都很难。

计算机科学家试图去解决这些 NP 问题，比较重大的成果就是量子计算机。量子计算机能解决部分 NP 问题，比如 RSA，很容易的分解很大很大的因数，世界显然就没有那么美妙了。当然，量子计算机也带来了量子加密算法以平衡这个世界，使之回归完美。