复杂问题的简单指南
复杂问题的简单指南原创： Kevin
原理
Yesterday
计算机能够做什么？又有哪些问题计算机几乎不可能解决？这些问题构成了计算复杂度的核心。这里，我们呈现了一张关于计算复杂度的地图：
https://mmbiz.qpic.cn/mmbiz_png/tqOuxs8dsHOzJL9JCzedsCqWdnibndxJYRgbuBLPkwR9ndcHgesjOO5w2iaQxtliaePvX6VKPkic4dibNthLTfibqUXQ/640?wx_fmt=png
○ 各种“复杂性类”（complexity class）将问题排序为层级结构：一个类可能包含另一个类的所有问题，以及其他需要额外计算资源的问题。
一个问题从本质上来说能有多难？这是计算机科学家的基本任务，他们希望将问题归类到所谓的复杂性类（complexity class）中。复杂性类包含所需计算资源少于一定数量的所有计算问题，这种计算资源通常指时间或内存。
以一个非常大的数字123456789001为例，一个问题可能会是：这个数字是质数、也就是只能被1和它自己整除吗？计算机科学家可以用快速算法（fast algorithm）解决这个问题，这种算法不会因为数字变得任意大而陷入停顿。对于123456789001这个例子，答案是它并不是质数。
然后我们可能会问：这个数字的质因数是什么？对于这个问题，并不存在第一个问题中的快速算法——除非使用量子计算机。因此，计算机科学家认为这两个问题属于不同的复杂性类。
存在许多不同的复杂性类，尽管大多数情况下，研究者还不能证明一个类完全区别于其他类。证明这些分类间的区别是该领域最困难和最重要的开放性问题之一，这就是为什么五月底Ran Raz和Avishay Tal这两位计算机科学家的证明结果被认为是如此重要。他们解决了科学家们自1993年就开始寻求答案的问题，证明了存在一些只有量子计算机能够解决、而无论现在或未来的经典计算机都永远不可能解决的问题，也就表明了量子计算机和经典计算机的两个复杂性类确实不同。（进一步阅读《误解带来的乐观与恐慌》）
复杂性类之间的差异可以是微妙的，也可以是明显的，如何正确分类是一个挑战。因此，我们将介绍以下10个基本的复杂性类作为一个入门，希望你看完后再也不会混淆BPP和BQP了。
P
代表：多项式时间（Polynomial time）
简单介绍：经典（非量子）计算机能够轻易解决的所有问题。
详细介绍：P类的算法必须在多项式时间 t=n^c 内停止并输出正确的结果，其中n是输入的长度，c是常数。
典型问题：
[*]一个数是质数吗？
[*]两点之间的最短路径是什么？
NP
代表：非确定性多项式时间（Nondeterministic Polynomial time）
简单介绍：只要给出一个解，经典计算机就能够快速验证给出的解是否正确的所有问题。
详细介绍：如果给定“是”的答案，可在多项式时间内确定这个答案是正确的，这就是一个NP问题。如果输入是一个字符串X，需要判断答案是否为“是”，那么这个简短的证明将是另一个字符串Y，然后，在多项式时间内，Y被用来验证答案是否为“是”。（Y有时被称为“短时见证”（short witness），NP类的所有问题都有“短时见证”，这些“短时见证”使得问题能够迅速被解决。）
典型问题：
[*]分团问题（Clique problem）
想象一个有边和节点的图形，例如Facebook的社交网络图，其中节点是个人，如果两个人建立好友关系，两个节点就被一条边连接。小团体（Clique）是整个图形的一个子集，其中每一个人都是其他人的朋友，也就是其中任意两个节点彼此连接。有人或许会问：存在20个人的小团体吗？50个人呢？100个人呢？寻找这样的小团体是图论领域的一个“NP完全”（NP-complete）问题，NP完全意味着这是NP类问题中最复杂的一种。然而，如果给出了一个潜在的答案，比如说50个节点可以或不可以形成一个小团体，那么问题就迎刃而解了。
https://mmbiz.qpic.cn/mmbiz_png/tqOuxs8dsHOzJL9JCzedsCqWdnibndxJYkfDjHcia8oa3rDAEdCXEKFA4kc3fbNqw8SxFVVKCHibfTJLeaVxibcM2A/640?wx_fmt=png○ 6个节点的网络图中大小为3的小团体。来源 | Wikepedia
[*]最短路径问题（Travelling salesman problem）
考虑一系列城市，其中每一对城市之间的距离是已知的，有没有一种方法能够以最短的距离穿越所有的城市呢？例如，一个旅行推销员能够穿越美国各个州的首府，而将行程控制在11000英里内吗？（进一步阅读：《一位旅行家》）
https://mmbiz.qpic.cn/mmbiz_png/tqOuxs8dsHOzJL9JCzedsCqWdnibndxJYsWibpnfh7yL6Nick6pwTbSQVc81weYS8ZhYdTuMsZbHzxhpPUSleuB7A/640?wx_fmt=png
○ 最短路径问题。来源 | Wikepedia
NP-Complete
代表：NP 完全
简单介绍：在多项式时间内，所有NP类问题都能够被规约到的问题的集合。
详细介绍：在多项式时间内，如果所有NP类问题都能被转化为另一个NP问题，那么这个转化后的NP类问题就称为NP完全问题。NP完全问题满足两个条件：1. 本身是NP类问题。2. 所有NP类问题都能规约到该问题。
典型问题：
[*]给一个整数集合，证明是否存在一个非空子集，使得该集合内的数字和为0。
NP-Hard
代表：NP困难
简单介绍：在多项式时间内，能够被规约到该问题的所有问题。
详细介绍：在多项式时间内，如果所有问题都能被转化为另一个问题，那么这个转化后的问题就称为NP困难问题。它满足NP完全问题的第二个条件，但不一定要满足第一条，即NP困难问题未必能在多项式时间内验证。
典型问题：
[*]停机问题（详见：《一个无法被证明的逻辑问题》）
https://mmbiz.qpic.cn/mmbiz_png/tqOuxs8dsHOzJL9JCzedsCqWdnibndxJYFf8bEIA8LI1QewxHpdaW02aibwZ6xnorTbfBp4JG7bttPzTh5PCh5tg/640?wx_fmt=png
○ 左侧是在假定P≠NP的前提下，P，NP，NP-Complete与NP-Hard四个复杂性类的关系，右侧则是假定P=NP的前提下它们的关系。 | 来源 Wikipedia
PH
代表：多项式层级结构（Polynomial Hierarchy）
简单介绍：PH是NP的外推，它包含NP类的所有问题，并在NP类问题的基础上，添加了额外的复杂度。
详细介绍：PH类包含一些交替使用比如“存在”、“每一个”、“所有”等“量词”（quantifier）的问题，使NP类问题更加复杂。一个关于交替量词问题的例子是：给定X，是否存在这样的Y，使得对于每一个Z，都存在这样的W，使得R成立？一个问题包含的量词越多，它就越是复杂，在多项式层级结构中的排序也就越高。
典型问题：
[*]确定是否存在规模为50的小团体，但不存在规模为51的小团体。
BPP
代表：有限错误概率多项式时间（Bounded-error Probabilistic Polynomial time）
简单介绍：在多项式时间内，可以通过包含随机性元素的算法快速解决，且通常输出结果的错误概率小于1/3的问题。
详细介绍：BPP与P唯一不同的是，BPP的算法允许包含随机决策的步骤。BPP的算法只需要以接近1的概率给出正确答案即可。
典型问题：
[*]给定两个不同的公式，每个公式产生一个包含很多变量的多项式，这两个公式计算的是相同的多项式吗？这个问题叫做多项式恒等检验问题。
研究人员想知道的是：BPP=P是否成立。如果这是真的，那就意味着每一个随机性算法都可以去随机化。他们相信这是事实，因为对于每一个存在有效随机性算法的问题，都有一个有效的确定性算法，但他们还不能证明这一点。
BQP
代表：有限错误量子多项式时间（Bounded-error Quantum Polynomial time）
简单介绍：在多项式时间内，量子计算机能够轻易解决的所有问题。
详细介绍：在多项式时间内，量子计算机能够轻易解决，且错误机率小于1/3的所有问题。
典型问题：
[*]确定一个整数的质因数。
计算机科学家已经证明：PSPACE包含BQP，且BQP包含P。关于BQP和NP这两个类的关系，有一些问题属于NP类，而不属于BQP类，反之亦然，两者互不包含。
https://mmbiz.qpic.cn/mmbiz_jpg/tqOuxs8dsHOzJL9JCzedsCqWdnibndxJYVpiamECMWEONsTkZyt4H8xuh74PTAKBcd5TLforc2gzhUXfMAqWnGkw/640?wx_fmt=jpeg
○ 计算复杂度地图上一块新区域：上文提到的五月底的研究，证明了存在属于BQP，却不属于PH的问题。（注：P-经典计算机能够快速解决的问题；NP-经典计算机就能够验证正确性的问题；NPC-NP完全问题；BQP-量子计算机能够有效决的问题。）
QMA
代表：量子梅林亚瑟（Quantum Merlin Arthur）
简单介绍：量子计算下的NP类问题。
详细介绍：在量子计算下，如果给定 “是”的答案，在多项式时间内，能够完成验证，确定这个答案正确与否，这就是QMA类问题。QMA类问题相对于BQP类问题的关系，就相当于NP类问题相对于P类问题，也就是验证与求解的复杂度的区别。
典型问题：
[*]局部哈密顿量问题。
PSPACE
代表：多项式空间（Polynomial Space）
简单介绍：PSPACE包含了所有只要用合理大小的内存（多项式量级的内存）就能解决的问题。
详细介绍：在PSPACE中，我们不关心时间，只关心运行算法所需的内存。
典型问题：
[*]P、NP和PH类的所有问题都包含在PSPACE中。
计算机科学家已经证明，PSPACE包含PH，PH包含NP，NP包含P。然而，对于P是否等于NP，是否等于PH，是否等于PSPACE，计算机科学家始终一筹莫展。P=NP问题是克雷数学研究所发布的七道难题之一，可以进一步阅读《一个价值百万美金的问题》了解更多。
EXPTIME
代表：指数时间（EXPonential Time）
简单介绍：在指数时间内，经典计算机能够解决的所有问题。
详细介绍：EXP包含之前所有的类——P、NP、PH、PSPACE、BQP和QMA等。研究人员已经证明，EXP不同于P，他们在EXP中发现了不属于P的问题。
典型问题：
[*]国际象棋和跳棋之类的游戏都属于EXP。如果棋盘可以是任意大小的，那么在给定的棋局形势下，确定哪一个棋手具有优势就是一个EXP问题。
计算机科学家想要证明PSPACE不包含EXP。他们认为EXP中有一些问题不包含在PSPACE中，因为有时候EXP类问题的解决需要大量的内存。计算机科学家知道如何区分EXP和P。
在计算复杂度的地图上，科学家们已经证明与尚未证明的问题可以总结如下：
https://mmbiz.qpic.cn/mmbiz_png/tqOuxs8dsHOzJL9JCzedsCqWdnibndxJYRP36p2ZxtqTdekuSXgfuiacYdKrk1pWIGTxQrrNV1SJvXjMGZEFklqQ/640?wx_fmt=png
从中可见，问题的源头主要在于那个价值百万美金的问题：P=NP是否成立。P是否等价NP的问题，可以简化为NP完全问题的证明，也就是证明，是否能用多项式级复杂度的算法来解决任何一个NP完全问题。
编译：仔仔审校：孙鹏参考链接：https://www.quantamagazine.org/a-short-guide-to-hard-problems-20180716/
页:
[1]