本节书摘来自华章计算机《计算复杂性：现代方法》一书中的第2章，第2.7节，作者 ［美］桑杰夫·阿罗拉（Sanjeev Arora），博阿兹·巴拉克（Boaz Barak），译 骆吉洲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.7　深入理解P、NP及其他复杂性类

2.7.1　NP的哲学意义

2.7.2　NP与数学证明

2.7.3　如果P=NP会怎样

如果P=NP——具体地讲，如果像3SAT这样的一个NP完全问题存在二次时间的高效算法——则世界很可能会变成一个计算乌托邦。数学家将会被高效的证明发现程序取代（该事实在哥德尔1956年的信中就曾被指出，并且20年后又重新被指出）。一般而言，对于答案能够被高效地验证（或正确性具有短证明）的任何搜索问题，我们将能够在多项式时间内高效地找到答案或短证明。人工智能(AI)软件将变得非常完美，因为对大型概率树的穷举搜索将很容易完成。发明家和工程师将可以借助各种软件包来为当前任务设计出完美的零部件。超大规模集成（VLSI）工程师将能够采用耗电量最小的最佳电路。58一旦科学家获得了一些实验数据，她将能够自动地找出解释这些实验数据的最简理论（对最简性需要选用合理的度量）；根据奥卡姆剃刀（Occam’s Razor）原理，最简单的解释很可能是正确的。然而，在某些情况下，科学家花费了几百年才找到解释已知实验数据的最简理论。这种方法也可以用来处理非科学问题。比如，可以从纽约《时代》杂志的最佳销售商列表中找出一个能够解释该列表的最简理论。（当然，找到“最简”的正确定义本身甚至就需要在人工智能和自然语言理解方面有所突破，以便NP算法能够在这两个领域中使用。）所有这些应用均是第5章将要研究的多项式分层的结果（找出最简“理论”的问题与第5章研究的MIN-EQ-DNF问题密切相关）。

有趣的是，计算乌托邦不需要考虑随机性。正如我们将看到的那样，如果P=NP，则在确定型算法中引入随机性并不能获得效率的提高，参见第7章。（这一点值得哲学家们深思。）

计算乌托邦需要付出的代价是：数字领域中不再存在隐私。任何加密方案均存在平凡的解码算法。数字货币、安全套接层(SSL)、公钥密码体系(RSA)和完美隐私(PGP)都将不存在（参见第9章）。这样，大家就必须学会在没有这些隐私保护机制下如何与人相处。

计算乌托邦显得很荒谬，然而我们却无法排除它存在的可能性。这一事实表明人类对计算的认识还少得可怜。从半全杯(half-full cup)的观点看，还存在大量精彩的事情有待发现。

2.7.4　如果NP=coNP会怎样

2.7.5　NP和NP完全之间存在其他复杂性类吗

2.7.6　NP难的处理

2.7.7　更精细的时间复杂性

本章学习内容

●类NP由成员资格存在多项式时间验证算法的所有语言构成。它包含了许多已知不属于P的重要问题。NP也可以用非确定型图灵机来定义。
●NP-完全问题是NP中最难的问题，其确切含义是，NP-完全问题存在多项式时间算法当且仅当P=NP。与图灵机似乎毫无关系的许多自然的问题已被证明是NP完全的。3SAT语言就是这样的例子，它由可满足的所有3CNF布尔公式构成。
●如果P=NP,则解能够被高效验证的任何搜索问题也能够被高效地求解。
●类coNP是由所有NP语言的补集构成的集合。人们相信coNP≠NP,它是一个比P≠NP还强的假设。

本章注记和历史