05 多项式谱系

直观上，在相同条件下最优化问题的难度高于存在性问题。判定一个解是否合法比判定该解是否是满足某最优条件的最优解要花费更多的计算资源。从逻辑刻画的角度，判定问题$L$形如$x \in L \iff \exists u \ \varphi(x,u)=1$。而最优解问题形如$x\in L \iff \exists u_1\forall u_2 \ \psi(x,u_1,u_2)$。所以直观上，一个$\text{NP}$问题的最优化问题的难度比$\text{NP}$更难。

$\texttt{MIN-DNF}$

比如，考虑一下$\texttt{MIN-DNF}$问题，它是一个$\lang \varphi,k\rang$的集合，其中的每个$\lang \varphi,k\rang$满足：存在一个长度不超过$k$的与$\varphi$有相同语义的DNF。也即$\texttt{MIN-DNF}=\{\lang \varphi,k\rang \mid \text{IsDNF}(\varphi) \land \exists \phi \ (\text{IsDNF}(\phi)\land |\phi|\leq k\land \forall u \ \varphi(u)\Leftrightarrow \phi(u))\}$。通过对$k$二分，这就可以看作是$\texttt{SAT}$的最优化版本：对于给定的$\varphi$，我们要判定$\varphi$是否是所有DNF的等价表述中长度最短的那个。

注意到，要验证$\lang \varphi,k\rang$是否属于$\texttt{MIN-DNF}$只需枚举所有长度不超过$k$的DNF，然后判定$\varphi \Leftrightarrow \phi$是否是个valid formula，也即是否成立$\varphi \Leftrightarrow \phi \in \texttt{SAT}$。因此，$\texttt{MIN-DNF}$可以被一个带神谕$\texttt{SAT}$的非确定性图灵机多项式时间解决。所以我们有$\texttt{MIN-DNF}\in\text{NP}^\texttt{SAT}$。既然$\texttt{SAT}$是$\text{NP}$-complete的，也就有$\texttt{MIN-DNF}\in \text{NP}^\text{NP}$。我们认为最优化问题的难度高于存在性问题的直观就是，$\text{NP}\subsetneq \text{NP}^\text{NP}$。

多项式谱系(Polynomial Hierarchy)

那么，什么样的问题是比最优化问题更难的问题？从逻辑刻画的角度，我们注意到由单个存在量词$\exists u,\varphi$变成$\exists u_1\forall u_2,\varphi$以后，可能加大了问题的难度——难度来自于存在量词与全称量词的交替。那么如果再出现一次量词的交替，比如$\exists u_1\forall u_2\exists u_3\forall u_4,\varphi$之后，难度可能进一步加大。我们注意到，这样一个存在量词与全称量词交替的形式恰好是我们曾定义过的$\texttt{QBF}$（量化布尔公式），它们可以看作一类二人博弈的形式。比如，围棋这一游戏的最优策略应当满足“你的任何一步棋我都能给出最佳的应对”，这就对应着量词的交替。

正如我们看到了交换一次量词让我们从$\text{NP}$类来到了$\text{NP}^\text{NP}$类，随着量词交换次数的不断增加我们能得到这一个复杂性类的谱系(hierarchy)：$\text{NP},\text{NP}^\text{NP},\text{NP}^{\text{NP}^\text{NP}},\text{NP}^{\text{NP}^{\text{NP}^\text{NP}}}$……尽管这个序列可以无限延续下去，但由于我们证明过$\texttt{QBF}$是$\text{PSPACE}$-complete的，因此这整个序列中的任何一个都应当属于$\text{PSPACE}$类（对应的直观是，对围棋最优策略的探索只需要棋盘大小的空间）。因此我们把这个谱系称为多项式谱系(polynomial hierarchy)。

为了方便表示，我们引入一下记号：

• $\Sigma^p_0=\text{P},\Sigma^p_{i+1}=\text{NP}^{\Sigma_i^p}$；
• $\Pi_i^p=\overline{\Sigma^p_i}$；
• $\Delta_{i+1}^p=\text{P}^{\Sigma_i^p}$；
• $\text{PH}=\bigcup\limits_{i\geq 0}\Sigma_i^p$；
• $\text{PH}_i=\Sigma_i^p\cup \Pi_i^p$，称为多项式谱系的第$i$层；

由定义可以验证，$\Sigma_i^p \subseteq \text{P}^{\Sigma_i^p}=\Delta _{i+1}^p \subseteq \text{NP}^{\Sigma_i^p}=\Sigma_{i+1}^p$，$\Pi_i^p=\overline{\Sigma_i^p}\subseteq \text{P}^{\Sigma_i^p}=\overline{\text{P}^{\Sigma_i^p}}=\Delta _{i+1}^p=\overline{\Delta _{i+1}^p}\subseteq \overline{\text{NP}^{\Sigma_i^p}}=\overline{\Sigma_{i+1}^p}=\Pi_{i+1}^p$。合并以上两个关系，有$\Sigma_i^p\cup \Pi_{i}^p\subseteq \Delta_{i+1}^p\subseteq \Sigma_{i+1}^p\cup \Pi_{i+1}^p$，这说明多项式谱系的每一层都包含上一层，也即我们对于“谱系”这一说法是well-defined的。

无限谱系假设

注意到，多项式谱系的第0层$\text{PH}_0=\text{P}$，第1层$\text{PH}_1=\text{NP}$。所以如果我们相信$\text{P}\neq \text{NP}$，就意味着相信多项式谱系的第1层严格包含第0层。我们自然地进一步推测，多项式谱系的每一层都严格包含前一层。这意味着相信从难度上，优化问题是严格难于判定问题的，等等。事实上，复杂性理论的很多定理都把这一假设作为前提（就好像把$\text{P}\neq \text{NP}$作为前提一样），我们把多项式谱系每一层都严格包含前一层这一假设称为无限谱系假设(Infinite Hierarchy Hypothesis)：$\forall i \in \N,\text{PH}_i\subsetneq \text{PH}_{i+1}$。

如果$\text{P}=\text{NP}$，那么$\Sigma_1^p=\text{NP}^\text{P}=\text{P}^\text{P}=\text{P}$, 归纳可得$\forall i\in \N,\Sigma_{i}^p=\text{P}$。这样就得到$\forall i\in \N,\text{PH}_i=\text{P}$。所以$\text{PH}=\text{P}$。此时多项式谱系坍缩成了多项式时间复杂性类。

如果对于某个$k$有$\Sigma_k^p=\Sigma_{k+1}^p$，也即如果多项式谱系的某一层发生了坍缩，那么容易证明$\text{PH}=\Sigma_k^p$，也就是这一层以后的谱系都坍缩到这一层。

还可以证明，如果对于某个$k$成立$\Sigma_k^p=\Pi_k^p$，那么$\text{PH}=\text{PH}_k$。可见$\Sigma_k^p$和$\Pi_k^p$只要有一方被完全被包含在另一方，谱系就会坍缩到这一层。

多项式谱系中的完全问题

Umans定理告诉我们，$\texttt{MIN-DNF}$是第二层中的完全问题（记为$\Sigma_2^p$-complete）。$\texttt{MIN-DNF}$是一个两个量词的量化布尔公式问题（$2$-$\texttt{QBF}$问题）。我们可以证明，$i$-$\texttt{QBF}$一定是$\Sigma_i^p$-complete的。

我们自然要追问，是否存在一个$\text{PH}$-complete问题？这其实是容易回答的。假如存在这样的一个问题$L$，那么一定存在一个$k$使得$L\in \text{PH}_k$。那么对任意$k'>k$，$\text{PH}_{k'}$中任何问题都可以归约到$\text{PH}_k$，可见$\text{PH}_k$之后的所有层都会坍缩到$k$层，导致$\text{PH}=\text{PH}_k$。

而既然存在$\text{PSPACE}$完全问题（比如$\texttt{QBF}$），所以如果$\text{PH}=\text{PSPACE}$，那么也就存在$\text{PH}$完全问题，谱系就会坍缩。所以只要我们相信无限谱系假设，就成立$\text{PH}\subsetneq \text{PSPACE}$。

交替图灵机(Alternating Turing Machine, ATM)

我们引入多项式谱系时，用的是计算的逻辑刻画。因为逻辑刻画表示存在量词和全称量词很方便。而在复杂性理论中，往往我们需要一个具体的类似图灵机的模型，这样通常会让解决问题变得方便。下面我们引入交替图灵机，它也刻画多项式谱系。

如何在图灵机的计算过程中引入量词？我们可以用一个类似非确定性图灵机的刻画。如果说确定性图灵机的计算过程是一个线性的链表，那么非确定性图灵机的计算过程就可以看作一棵二叉树。从量词的角度，我们可以认为非确定性图灵机的计算过程本身带有全称量词$\forall$。那么我们可以取非确定性图灵机的整棵二叉树的一个导出子树，在含有全称量词的状态让节点的两个子节点都落在导出子树中，在含有存在量词的状态让节点有至少一个节点落在导出子树中，这样就把量词引入了图灵机。下面严格地定义交替图灵机：

交替图灵机是一台非确定图灵机，其每个非终止节点上带有一个额外的标记，这个标记要么是$\exists$要么是$\forall$。称交替图灵机$\mathbb{A}$接受输入$x$，如果该非确定性图灵机的状态树上存在一个导出子树，满足：根节点在导出子树内；叶节点恰好是所有的接受状态；标记为$\forall$的节点的两个儿子都在导出子树中；标记为$\exists$的节点至少有一个儿子在导出子树中。

因为交替图灵机是非确定性图灵机，所以其时间函数和空间函数的定义可以继承非确定性图灵机，也即所有计算路径上的时间都不超过其时间函数，所有计算路径的空间都不超过其空间函数。分别记为$\text{ATIME, ASPACE}$，类似地可以定义$\text{AP},\text{AEXP},\text{AL},\text{APSPACE}$等的复杂性类。

Chandra-Kozen-Stockmeyer定理：

• $\text{NSPACE}(S(n))\subseteq \text{ATIME}(S^2(n))$：？

• $\text{ATIME}(S(n))\subseteq \text{SPACE}(S(n))$：？

• $\text{ASPACE}(S(n))\subseteq \bigcup\limits_{c>0}\text{TIME}(c^{S(n)})$：？

• $\text{TIME}(S(n))\subseteq \text{ASPACE}(\log S(n))$：？

根据Chandra-Kozen-Stockmeyer定理，容易得到$\text{AP}=\text{PSPACE}$，$\text{AL}=\text{P}$，等等。可见，从指数增长的谱系角度，我们有：经典图灵机的某一时间复杂性类等于交替图灵机同量级的对数的空间复杂性类；经典图灵机的某一空间复杂性类等于交替图灵机同量级的时间复杂性类。特别地，$\text{AP}=\text{PSPACE}$告诉我们多项式谱系中的问题都可以用交替图灵机多项式时间判定。

自然地，我们可以通过量化布尔公式的交替图灵机判定方法刻画多项式谱系。