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

7种计算复杂类的关系

导语

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

根据不同的复杂类别可以把问题排列成如上图的层级状：某些类别能包含其他类别中的所有问题，同时还包含需要额外计算资源的其他问题。一个问题到底有多难？对于那些想把所有问题按照复杂类别(complexity claesses)排序的计算机科学家来说，这是一个最基本的任务。一个复杂类别包含了满足特定条件的所有计算问题：这些问题的时间和空间复杂度不超过某个值。举个简单的例子，对于整数123456789001，有些人可能会问：这个数是一个质数吗？计算机科学家可以使用一个快速算法解决这个问题，并且该算法对于任意大的数仍适用。在我们的例子中，123456789001不是质数，那么它的质数因子是什么呢？对于这个问题，就不存在上述快速算法了，当数变得相当大时，算法的时空复杂度会变得不切实际——如果你有量子计算机的话当我没说。因此，计算机科学家相信上述两个问题（判断是否为质数 | 找到非质数的质数因子）属于不同的计算复杂类别。7个计算复杂类别计算复杂类别有很多种，虽然大多数情况下研究者不能证明某个类别和其他类别截然不同。而证明这些复杂类别之间的关系是该领域最困难和最重要的开放性问题。复杂类之间的可能只有微妙的差异，也可能有着显著的差异，弄清楚类别之间的差异还挺有挑战性。为此，本文把最基本的七个复杂类别放在一起，希望你看完后不要再混淆BPP和BQP了：）P全称：多项式时间（Polynomial time)简述：能用经典计算机轻易解决的所有问题精确描述：

典型问题：

研究者们关心：

NP全称：不确定多项式时间 （Non-deterministic Polynomial time)简述：能用经典计算机快速验证答案的所有问题精确描述：

典型问题：

研究者们关心：

PH全称：多项式层级 (Polynomial Hierarchy)简述：PH是NP问题的一种扩展，如果一个问题开始是NP，但是随后会增加额外的复杂性，那么该问题就属于PH。精确描述：

典型问题：

研究者们关心：

PSAPCE全称：多项式空间 （Polynomial Space）简述：PSPACE包含了所有可以通过合理内存来解决的问题精确描述：

典型问题：

研究者们关心：

BQP全称：有界误差量子多项式时间 （Bounded-error Quantum Polynomial time）简述：所有能用量子计算机快速解决的问题精确描述：

典型问题：

研究者们关心：

EXPTIME全称：指数时间 （Exponential Time）简述：所有能用经典计算机在指数级时间内解决的问题精确描述：

典型问题：

研究者们关心：

BPP全称：有界误差概率多项式时间 （Bounded-error Probabilistic Polynomial time）简述：可以通过包含随机因素的算法快速解决的问题精确描述：

典型问题：

研究者们关心：

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

每日小知识分享：每一个 HTML 文档中，都有一个不可或缺的标签：，在几乎所有的HTML里， 我们都可以看到类似下面这段代码：

head标签作为一个容器，主要包含了用于描述 HTML 文档自身信息（元数据）的标签，这些标签一般不会在页面中被显示出来，主要告知搜索引擎本页面的关键字以及对应网址，在SEO中传递相关权重起到非常重要的作用。