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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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