P，NP，PSPACE都是什么？一文讲清计算复杂性分类

7种计算复杂类的关系

导语

对于计算机来说，哪些问题是容易计算的，哪些是几乎不可能的？这些是计算复杂性领域的核心问题。本文是对这些问题的鸟瞰。

关键词：计算复杂性

Kevin Hartnett | 作者

高飞 | 译者

王怡蔺 | 编辑

根据不同的复杂类别可以把问题排列成如上图的层级状：某些类别能包含其他类别中的所有问题，同时还包含需要额外计算资源的其他问题。

一个问题到底有多难？对于那些想把所有问题按照复杂类别 (complexity claesses) 排序的计算机科学家来说，这是一个最基本的任务。一个复杂类别包含了满足特定条件的所有计算问题：这些问题的时间和空间复杂度不超过某个值。

举个简单的例子，对于整数123456789001，有些人可能会问：这个数是一个质数吗？计算机科学家可以使用一个快速算法解决这个问题，并且该算法对于任意大的数仍适用。

在我们的例子中，123456789001不是质数，那么它的质数因子是什么呢？对于这个问题，就不存在上述快速算法了，当数变得相当大时，算法的时空复杂度会变得不切实际——如果你有量子计算机的话当我没说。

因此，计算机科学家相信上述两个问题（判断是否为质数 | 找到非质数的质数因子）属于不同的计算复杂类别。

7个计算复杂类别

计算复杂类别有很多种，虽然大多数情况下研究者不能证明某个类别和其他类别截然不同。而证明这些复杂类别之间的关系是该领域最困难和最重要的开放性问题。

复杂类之间的可能只有微妙的差异，也可能有着显著的差异，弄清楚类别之间的差异还挺有挑战性。为此，本文把最基本的七个复杂类别放在一起，希望你看完后不要再混淆BPP和BQP了：）

P

全称：多项式时间（Polynomial time)

简述：能用经典计算机轻易解决的所有问题

精确描述：

• P类中的算法必须在n^c的时间内停止并给出正确答案，其中n是输入的规模，c是常数

典型问题：

• 一个数是否是质数？

• 两点之间的最短路径是什么？

研究者们关心：

• P和NP是一回事吗？如果P=NP，那么计算机会被颠覆，大多数密码技术会在一夜之间失效。（几乎没人认为这是成立的。）

NP

全称：不确定多项式时间

（Non-deterministic Polynomial time)

简述：能用经典计算机快速验证答案的所有问题

精确描述：

• 如果给出某问题一个答案，存在对答案正确性的简短的证明，那么该问题就是一个NP问题。如果输入一个字符串X，你需要确认答案的是否是“YES”，那么上述简短的证明指另外一个字符串Y，这个字符串可以用来在多项式的时间内验证答案是否是“YES”。

（Y时常被成为“short witnesses”——所有的NP问题都有“short witnesses”使其能快速验证答案）

典型问题：

• 团问题 (clique problem)：

想象一张点和边组成的图，例如Facebook上用户为点，朋友关系为点之间的连边所组成的图。团 (clique) 是指节点全连接的子图。

人们也许会问：存在包含20个人的团吗？50个呢？100个呢？找到这样的团是一个“NP完全 (NP-complete) ”的问题，意为该问题在NP问题中具有最高的复杂度。但是给定一个20个人组成的子图，很容易检验该子图是否是正确答案。

这就是NP问题的特点，很难找到正确的解，但是判断一个解是否正确十分容易；

• 旅行商问题 （The traveling salesman problem）:

给定一些相互远离的城市，是否存在一条穿过所有城市的路径，路径长度小于给定值？例如，是否有一条路径能经过美国所有的州府，总距离却不超过11,000英里？

研究者们关心：

• P=NP吗？而计算机科学家现在根本没法解决这个问题，这个问题也是信息学领域的最高峰。

PH

全称：多项式层级

(Polynomial Hierarchy)

简述：PH是NP问题的一种扩展，如果一个问题开始是NP，但是随后会增加额外的复杂性，那么该问题就属于PH。

精确描述：

• PH中的问题都包含一些交替的量词，使得问题变得更加复杂。例如，给定X，是否存在一个Y，使得对于所有的Z，都存在一个W使得R为真？问题中包含的量词越多，问题越复杂，问题在多项式层级中越高。

典型问题：

• “存在一个大小为50且不存在大小为51的团”是否为真？

研究者们关心：

• 计算机科学家还没能证明PH是与P不同的。这个问题是和P=NP等价的，因为：如果 P=NP，则所有的 PH 可归化到 P，也即 P=PH。

PSAPCE

全称：多项式空间

（Polynomial Space）

简述：PSPACE包含了所有可以通过合理内存来解决的问题

精确描述：

• 在PSAPCE类的问题中，你不在乎时间，只关心一个算法所需的内存空间。计算机科学家已经证明PSPACE包含PH类，而PH类包含NP，同时NP还包含P类。

典型问题：

• P, NP, PH类中的所有问题，都属于PSAPCE类

研究者们关心：

• P和PSPACE不同吗？

BQP

全称：有界误差量子多项式时间

（Bounded-error Quantum Polynomial time）

简述：所有能用量子计算机快速解决的问题

精确描述：

• 所有能用量子计算机在多项式时间内解决的问题

典型问题：

• 确定整数的素因子

研究者们关心：

• 计算机科学家们已经证明，BQP包含在PSPACE中，且BQP包含P。但是他们不知道BQP是否包含在NP中，但是他们相信这两类是不可比的：存在NP中的问题但不是BQP，反之亦然。

EXPTIME

全称：指数时间

（Exponential Time）

简述：所有能用经典计算机在指数级时间内解决的问题

精确描述：

• EXP包含前面的所有类：

P,NP,PH,PSAPCE,BQP。

研究者已经证明EXP与P不同，因为他们呢已经发现了在EXP而不在P中的问题。

典型问题：

• 像象棋和跳棋一类游戏的扩展都属于EXP。如果象棋棋盘能是任何大小，那么在给定棋局时，确定哪位棋手更加有优势，便是一个EXP问题。

研究者们关心：

• 计算机科学家能够证明PSAPCE并不包含EXP。他们认为在EXP中存在不属于PSPACE的问题，因为有些EXP问题需要用大量内存才能解决。计算机科学家们知道如何将EXP和P这两类问题分开。

BPP

全称：有界误差概率多项式时间

（Bounded-error Probabilistic Polynomial time）

简述：可以通过包含随机因素的算法快速解决的问题

精确描述：

• BPP与P完全相同，但是该类问题允许算法在某些步骤包含随机因素。BPP中的算法只需给出概率趋近于1的正确答案。

典型问题：

• 让你处理两个不同的公式，每个公式都产生包含多个变量的多项式。两个公式会是否计算的相同的多项式吗？这就是所谓的多项式身份测试问题。

研究者们关心：

• 计算机科学家们想知道BPP=P是否成立。如果成立，即所有的随机算法都可以去随机化。他们认为情况确实如此——对于每个存在有效随机算法的问题，都存在一个有效的非随机算法——但是他们还无法证明这点。

读到此处的读者，再回到文首看一看复杂类的层级图，一定会觉得更加清楚明了！

来源：quantamagazine

原题：A Short Guide to Hard Problems

原文：

https://www.quantamagazine.org/a-short-guide-to-hard-problems-20180716/

原标题：《P，NP，PSPACE都是什么鬼？一文讲清计算复杂性分类》

阅读原文