大家如果想更多的了解P和NP的问题，可以去看看2009年的综述论文，或者一些其他的科普书籍自行了解。也有一些比较偏正式的介绍工作，比如Michael Garey 和 David Johnson在1979年出版的书籍，他们的这本书对于想了解NP完全问题的读者来说一定不能错过：Garey, M. and Johnson, D. Computers and Intractability. A Guide to the Theory of NP-Completeness.W.H. Freeman and Company, New York, (1979).
文章插图
在1971年的那个星期二的下午，Cook在ACM计算理论研讨会上发表他那篇关于NP完全的论文时，他证明了可满足性是NP完全的，而重言式是NP难的。论文中也推断说Tautology是不具备P特性的一个问题，当然，当时没有对这个问题进行很好的证明。但无论如何，这篇论文以及其中的证明方法，标志着复杂性理论的重大突破。想要去证明一个数学概念通常具有很大挑战。算法和证明的基础概念至少可以追溯到古希腊时期，当然，他们从来没考虑过NP和P这样的问题。高效计算和非确定性的理论基础是在1960年代才发展起来的。但P和NP的问题在这之前很久就已经被提出来了，只是我们没有给它们正式冠名而已。库尔特·哥德尔在1956年曾经写过一封给冯·诺依曼的信。在信中他就初步描述了P和NP问题。这封信直到1988年才被发现，并广为流传。Richard Karp真正意义上首次将P和NP问题引入大家视野。他在1972年的论文中介绍了该问题，并随后得到广泛的关注。我们知道很多有名的组合问题都是NP完全的，包括Clique, 3-coloring和旅行商问题。1973年，当时在俄罗斯的Leonid Levin在他两年前独立研究结果的基础上发表了一篇新的论文，并在这篇论文中定义了P和NP问题。当Levin的论文传播到西方的时候，P和NP问题也已经确立了作为计算领域最重要问题的地位。Russell Impagliazzo在1995年的一篇经典的论文中描述了P和NP问题具有不同程度可能性的5个层级：
- 算法：P=NP或理论上等效，例如NP的快速概率算法(fast Probilistic algorithm)
- 启发式：NP问题在最坏的情况下很难求解，但平均来说还是可以得到求解的
- Pessiland：我们可以轻松的创建困难的NP问题，这是所有可能中最糟糕的，因为我们既不能在平均意义上解决难题，也不能从这些问题的难度中获取任何明显的优势
- Minicrypt：存在加密的单向函数的问题，但我们没有公钥加密
- Cryptomania：公钥密码学，也就是说，两方可以通过公开渠道来交换加密信息，然后通过公钥解密
上述的5个层级没有正式的定义，都是通过人们对P和NP问题的了解人为规定的。但是人们普遍认为，Cryptomania这个等级的可能性最高。Impagliazzo借鉴了P和NP理论中的核心思想——“我们无法拥有一切”。我们或许可以解决困难的NP问题，或者解决密码学的重要关键，但是不能将两者同时攻克。不过，也许我们正在走向事实上的Optiland——机器学习和软硬件优化等方面的长足进步让我们能够在一定程度上解决当年无法设想的问题，包括语音识别、蛋白质折叠解析等。但是大多数情况下，我们的密码协议仍然是安全的，所以不用太担心。在2009年的综述中，我曾经在其中“如果P=NP怎么办”的章节中提出，通过使用奥卡姆剃刀法则，学习将会变得容易——我们只需要找到与数据一致的最小程序，也就是问题的关键核心。那么此时，原本十分难以解决的视觉识别、语音识别、翻译以及其他的任务都会变得微不足道。我们还将对天气、地震和其他自然现象做出更好的预测和理解，以及建模。今天，我们可以使用人脸识别解锁手机，可以和一些智能设备语音对话来提出问题并且得到理想的回答，可以将我们说的话、输入的文字翻译成另外的语言。我们的手机会收到关于天气和其他突发事件的警报，它的预测效果比我们之前十几年前能做到的效果好的多。与此同时，除了对小密钥长度进行类似暴力破解的攻击之外，我们的密码学基本上还是很鲁棒和安全的。那么现在，让我们看看计算、优化和学习方面的最近进展如何将我们带到Optiland中吧！
