“复杂度动物园”中的“俄罗斯套娃”
大家好，我是大老李。上一期我们聊了什么是“时间复杂度”和“P vs NP”问题。 上期结尾留下一个疑问是：除了P和NP问题外，还有其他复杂度的问题吗？答案是肯定的，而且非常多。科学家对不同的可以用算法求解的问题分类了多达数百种的复杂度，有人称其为“复杂度动物园”。但是动物园里的动物太多了，我们一般爱好者没有必要了解那么多。
但大老李可以带大家了解其中最主要的一组复杂度，而且它们是沿着P和NP问题自然延伸的，所以比较容易记忆。 上一期我们了解到P问题是NP问题的子集，接下来大老李要介绍的一组复杂度，它们的特点都是：前一个复杂度都是后一个的子集。所以它们像俄罗斯套娃一般套在一起，越后面的复杂度，越复杂，它也会包含之前所有复杂度的问题。
第一个要介绍的复杂度叫PH问题(Polynomial Hierarchy)，中文可以叫做：“多项式层级问题”。PH问题是NP问题的一般化，它的一种定义是：“能以二阶逻辑所表示语言的集合”。对“二阶逻辑”，大老李之前在“不可证明的证明”那一期节目提到过，这里可以再简单介绍下。
很多数学命题都以“存在”，或者“对任意”这两个关键字开始。比如上一期提到的小圈子问题：“存在一个6人小圈子”，使得这6个人其他人都不是好友关系”。这个命题就是以“存在”二字开始。但如果一个命题同时有多个“存在”和“对任意”这两个关键词的话，这个命题的复杂度就会增长。比如把“小圈子”命题增强一下，改为“存在一个6人小圈子，使得这6个人其他人都不是好友关系，且不存在一个7人的小圈子，使这7人与其他人都不是好友关系”。你看，这个命题是不是要比之前的命题强许多？这种出现两个“存在”或“对任意”关键词的命题，往往就是“二阶逻辑”命题。
当然，我还可以增强下之前的命题，改成：对6-100之间的所有自然数n，存在一个n人小圈子，且不存在一个n+1人的小圈子”。虽然这个命题肯定是假命题，但是它的描述复杂度要比之前的更增加许多。总之，PH问题就是通过逻辑上的递归，使得表述复杂度层叠递增的那些命题，它是NP问题的一般化。当然，所有NP问题都是PH问题。
而且科学家发现，如果“P问题=NP问题”，则可以推出“P=PH”，这说明PH问题相比于NP并没有出现复杂度本质上的增加。所以反过来证明PH!=P，也许是一个证明P!=NP的思路。以上是有关PH问题。
接下来介绍的一个复杂度叫“多项式空间”问题，英语叫“P-SPACE”。这里“P”还是“多项式”的意思，“Space”就是英语“空间”一词。之前我们都是考虑的时间复杂度，但是一个算法运行时，不但要消耗时间，同样要消耗内存，这个内存我们可以抽象为“空间”。我们问：一个算法的处理对象增加时，其消耗的内存增加程度如何？这就是”空间复杂度”。那“多项式空间”复杂度就太容易理解了，就是程序随处理对象增加，其消耗的内存量是按多项式增加的。
科学家已经证明所有PH问题都是“多项式空间问题”，推论就是：所有NP问题都是“多项式空间问题”，这一点还是可以用化归思想简单证明：
当求解一个NP问题时，我们只需要保留我们已经枚举过的情况序号。还是以“小圈子问题”为例，当我们不考虑时间消耗时，我们可以用枚举法暴力求解，则我们需要对n个人里取6个人的组合的情况一一枚举。这种枚举组合可以通过循环语句构造出来，而不需要事先在内存里保留所有组合。只需要枚举一种，检查是否为小圈子，如果不是，则丢弃这种组合，枚举下一种等等，这样算法的内存消耗几乎是个常量，所以这个“小圈子问题”是一个“多项式空间问题”。用类似方法，可以证明NP问题都是多项式空间问题。
但是否存在某个多项式空间问题不是NP问题？这是未解决的问题。目前找到的一些可能的问题是有关棋类游戏的问题，比如围棋的官子问题。围棋是一种确定性的博弈问题，如果到了官子阶段，还剩十几二十个位置可以下，理论上可以画出一棵完整博弈树，把双方从开始到结尾的每一步的组合都出来。
那么从这棵博弈树里找出最佳着法的一种算法，人称“极小-极大算法”（ min-max算法），其实就是模拟人脑计算的一个过程：我下一步的最佳着法，就是对方在他的下一步采取最佳着法时，我的最佳着法。 而对方下一步的最佳着法，又是我的下下一步最佳着法前提下，他的最佳着法，依此类推，如此递归验算到最后一步，再反向回溯，就能找到双方的最佳着法。
对以上算法考察空间复杂度的话，你会发现你只需要存储博弈树某一层的一个或几个着法。如果这一层是我落子，那就存储我的最佳着法，如果下一层是对方落子，则存储对方最佳着法。如此推算，则我需要的存储的空间应该是正比例于博弈树的深度，博弈树的深度一般就是可落子的位置数，所以以上算法是“多项式空间”算法。这也是可以理解的，如果围棋的计算需要指数级的空间增长 ，大概谁的脑容量都无法计算了。
但是官子问题看上去又不是一个NP问题。如果给你一个双方官子落子的顺序，你如何用算法判断出这是否是双方最佳官子顺序呢？如果用以上“极小-极大算法”，其时间复杂度肯定是“指数时间”，你也不能说九段高手的判断就一定正确。所以目前没有一个能在多项式时间内，判定某个官子顺序是否最佳的算法，因此围棋官子问题是一个属于“多项式空间问题”，而看起来不是“NP问题”的问题。
比“多项式空间问题”更复杂一级的， 就是大家熟悉的“指数时间问题”，意思就是”算法执行时间随问题规模成指数增长。同样，所有“多项式空间问题”都是“指数时间问题”。如何把“多项式空间问题”化归为“指数时间问题”，我就留给听众思考，这是一道不错的思考题。
另一方面，如你所猜测，目前科学家还没有证明：存在某个问题，它是“指数时间问题”，但不是“多项式空间问题”。也就是，这个问题需要指数时间的计算，也肯定需要指数级的内存消耗。一个完整的国际象棋或者围棋博弈问题，可能是符合前述条件的，但目前无法证明。
以上，我们构建了一条复杂度链条，从简单到复杂是：NP, PH，多项式空间和指数时间。上一期我们还谈到了P是NP的子集。有意思的是，P与NP之间，人们在研究量子计算机过程中，还定义两种介于P与NP之间的复杂度。
首先的一种名叫：BPP问题（Bounded-error Probabilistic Polynomial time），中文可以叫做：“具有有界错误概率的多项式时间算法”。顾名思义，BPP问题首先具有一个多项式时间算法，但我们允许这种算法有一定的错误概率，但这个错误概率必须足够小，有一个固定的上界。
根据定义，P问题显然都是BPP问题，因为对P问题来说，这个错误率上界就是0。但BPP问题的算法可能输出错误结果，那它有什么意义呢？当然有。比如对NP问题，我们知道枚举所有情况所需时间太久了，那实际求解时，我们当然不会总是傻傻地开始枚举。
我们可以用一些“启发式”手段，来尽量找到合理的解。比如你让我求解“三色地图着色问题”，我肯定会随便尝试对某个区域画一种颜色，然后从这个区域扩散出来，尽量使用三种颜色，这是每个人都能找到的思路。
也许中途，我会发现没法继续着色，产生冲突了，这样就不得不在之前某一步推倒重来。但我可以规定，我就从地图中每个区域为起始，对它分别尝试三种不同颜色的起始情况。这样，如果图中有n个区域，尝试最多3乘以n轮之后，仍然没有答案的话，我就宣告“无解”。
用电脑程序完全可以模拟以上过程，这个算法能够在多项式时间内结束。如果有解，那是最好；如果“无解”，那么这个“无解”是有一定错误概率的，因为没有枚举到所有情况。但是我可以说，我已经尝试了很多次，这个错误率应该是很低的，并且我能证明错误率是%5以下等等。这种算法在实践中是很有用的，因为很多情况下，我们希望在一定时间内得出一个结果，哪怕它有一定错误几率，这总比等不到结果好。以上就是BPP问题的含义。
最后一个复杂度叫BQP（Bounded-error Quantum Polynomial time）问题，中文叫“具有有界错误概率的量子多项式时间”，其实就比BPP问题多了“量子”二字。这种问题的一个简单定义就是：可以用量子计算机快速（在多项式时间内）处理的问题。那量子计算机与传统计算机的关键区别在哪里呢？
上一期提到过，NP问题可以依靠“堆CPU”来快速求解，只要让不同的电脑分别验证不同的情况。而量子计算机利用了量子的“叠加态”，可以用少数几个量子，来模拟非常多的CPU进行并行运算，并且通过量子最后“坍缩”结果，来得到我们需要的结果。这样很多NP问题就成为多项式时间问题了，这也是我们研发量子计算机的一个最主要动力。
但是，另一方面量子的行为是不受控的，都是“概率性”的行为，“计算”结果总是会有误差的。按“平行宇宙”理论说法，每次“测量”量子计算机的计算结果后，有些宇宙中的我们得到了正确的结果，有些则只能得到错误的结果。但好在错误概率是可以计算的，大不了我就多算几次吧。多做几次后，可以让错误率降低到可以接受的程度。
但不管怎样，总有误差，所以量子计算机可以快速处理的问题被叫做：“具有有界错误概率的量子多项式时间”问题，简称BQP问题。目前一个典型的BQP问题是质因数分解问题。之前说过，判断一个数是否为质数，是一个P问题，但是判断出一个数不是质数，并不表示我们能对这个数进行质因数分解。目前传统计算机上最快的质因数分解算法是一个接近于指数时间 (
)的算法。
而1994年，数学家彼得· 秀尔提出了一个质因数分解的量子算法，其复杂度只有
，所以是一个标准的多项式时间问题，因此质因数分解就是一个BQP问题。这也是为何我们说，一旦量子计算机突破到某个“量子霸权”时刻，一些加密算法会失效，就是因为一些加密算法依赖我们无法快速进行质因数分解这一前提。
但是不是所有的NP问题都是量子计算机都能快速求解的？目前科学家还不能证明，但科学家倾向于认为NP问题与BQP问题是互不包容的。即存在一些NP问题，是量子计算机不能快速求解的，也存在一些BQP问题，是比NP问题更复杂的，即无法再多项式时间内检查答案的。但这都是有待证明的领域。
好了，以上就是今天关于“复杂度动物园”的介绍，复习一下几个要点：
算法复杂度分类多达数百种，但它们之间许多有包含的关系。
以下这组复杂度，从简单到复杂，有点像俄罗斯套娃，层层嵌套：它们是：P问题, NP问题，PH问题，多项式空间问题，指数时间问题。其中之前的每一个都是后面的复杂度的子集，但除NP与PH问题外，其他每两种复杂度之间是否是“真子集”（即，是否可以排除“等于”）关系，都还未证明。
以下这组复杂度，也构成一组“套娃”：P问题，BPP问题，BQP问题。
科学家认为BQP问题，即量子计算机能快速处理的问题，虽然含有很多NP问题，但与NP问题互不包含。但这仍然是待证明的领域。
好了，下期再见！
参考链接：
https://en.wikipedia.org/wiki/PSPACE
https://en.wikipedia.org/wiki/P_versus_NP_problem
A Short Guide to Hard Problems | Quanta Magazine
https://zh.m.wikipedia.org/zh-hans/PH_(%E8%A4%87%E9%9B%9C%E5%BA%A6)
Complexity Zoo:N
