多项式谱系

计算复杂度理论中，多项式谱系是一个复杂度系列。它从P、NP和反NP复杂度类逐级产生至预言机。它类似于数理逻辑中算数阶层和分析阶层，只不过是由逐级放宽资源限制而产生的。

## 定义

多项式谱系有数个等价的定义。

用预言机定义多项式谱系。首先定义

$$\Delta_0^\mathsf{P} := \Sigma_0^\mathsf{P} := \Pi_0^\mathsf{P} := \mathsf{P},$$

其中P是能在多项式时间内解决的决定性问题。然后对所有$i \ge 0$定义

$$\Delta_{i+1}^\mathsf{P} := \mathsf{P}^{\Sigma_i^\mathsf{P}}$$

$$\Sigma_{i+1}^\mathsf{P} := \mathsf{NP}^{\Sigma_i^\mathsf{P}}$$

$$\Pi_{i+1}^\mathsf{P} := \mathsf{coNP}^{\Sigma_i^\mathsf{P}}$$

其中$\mathsf{P}^{\rm A}$是在有${\rm A}$类中某些完备问题的预言机辅助的情况下，能在多项式时间内由图灵机解决的决定性问题的集合。类别$\mathsf{NP}^{\rm A}$和$\mathsf{coNP}^{\rm A}$也有类似的定义。比如，$\Sigma_1^\mathsf{P} = \mathsf{NP}$、 $\Pi_1^\mathsf{P} = \mathsf{coNP}$和$\Delta_2^\mathsf{P} = \mathsf{P^{NP}}$是一些能在某些NP完全问题预言机的辅助下，在多项式时间内解决的问题的复杂度类。

用存在状态或者全称状态定义多项式谱系。令$L$为一个语言（或称为决定性问题，即$\{0,1\}^*$的某个子集），$p$为某多项式，定义

$$\exists^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \exists w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\},$$

其中$\langle x,w \rangle \in \{0,1\}^*$为某种将二进制字符串对$x$和$w$编码为一个二进制字符串的标准编码。$L$代表一个有序的字符串对的集合，其中第一个字符串x是$\exists^p L$的元素，而第二个字符串$w$是一个足够短的（长度不大于$p(|x|)$）见证$x$在$\exists^p L$内的字符串。换句话说，$x \in \exists^p L$当且仅当存在足够短的见证字符串$w$使得$\langle x,w \rangle \in L$。类似地，定义

$$\forall^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \forall w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\}$$

注意到由德摩根定律得出$\left( \exists^p L \right)^{\rm c} = \forall^p L^{\rm c}$ and $\left( \forall^p L \right)^{\rm c} = \exists^p L^{\rm c}$，其中$L^c$是$L$的补集。令$\mathcal{C}$为一个语言集。延伸这些运算使得它们能够应用于语言集上：

$$\exists^\mathsf{P} \mathcal{C} := \left\{\exists^p L \ | \ p \in \mathcal{P}, L \in \mathcal{C} \right\}$$

$$\forall^\mathsf{P} \mathcal{C} := \left\{\forall^p L \ | \ p \in \mathcal{P}, L \in \mathcal{C} \right\}$$

其中$\mathcal{P}$为所有多项式的集合。同样德摩根定律成立$\mathsf{co} \exists^\mathsf{P} \mathcal{C} = \forall^\mathsf{P} \mathsf{co} \mathcal{C}$以及$\mathsf{co} \forall^\mathsf{P} \mathcal{C} = \exists^\mathsf{P} \mathsf{co} \mathcal{C}$，其中$\mathsf{co}\mathcal{C} = \left\{ L^c | L \in \mathcal{C} \right\}$。

复杂度类NP和反NP可被定义为$\mathsf{NP} = \exists^\mathsf{P} \mathsf{P}$和$\mathsf{coNP} = \forall^\mathsf{P} \mathsf{P}$, 其中P是所有可行的（多项式时间内的）递归语言。则多项式谱系可被递归定义为

$$\Sigma_0^\mathsf{P} := \Pi_0^\mathsf{P} := \mathsf{P}$$

$$\Sigma_{k+1}^\mathsf{P} := \exists^\mathsf{P} \Pi_k^\mathsf{P}$$

$$\Pi_{k+1}^\mathsf{P} := \forall^\mathsf{P} \Sigma_k^\mathsf{P}$$

注意$\mathsf{NP} = \Sigma_1^\mathsf{P}$, and $\mathsf{coNP} = \Pi_1^\mathsf{P}$。这个定义反映出多项式谱系和算数阶层之间的紧密关系。其中R和RE分别扮演了类似P和NP的角色。算数阶层同样是用一系列的实数子集来定义的。

用交替式图灵机的等价定义。定义$\Sigma_k^\mathsf{P}$（或$\Pi_k^\mathsf{P}$）为从存在状态（或全称状态）开始的$k$次交替式图灵机能够解决的问题的集合。

## 多项式谱系类别之间的关系

<image>

由定义可推论出如下关系：

$$\Sigma_i^\mathsf{P}\subseteq \Delta_{i+1}^\mathsf{P} \subseteq \Sigma_{i+1}^\mathsf{P}$$

$$\Pi_i^\mathsf{P} \subseteq \Delta_{i+1}^\mathsf{P} \subseteq \Pi_{i+1}^\mathsf{P}$$

$$\Sigma_i^\mathsf{P} = \mathsf{co}\Pi_i^\mathsf{P}$$

算术阶层和分析阶层中各层次包含关系都已确定为真包含，而多项式谱系中的这些包含关系是否为真包含仍未有定论，但人们普遍相信它们是真包含。如果任一$\Sigma_k^\mathsf{P}=\Sigma_{k+1}^\mathsf{P}$，或者$\Sigma_k^\mathsf{P}=\Pi_k^\mathsf{P}$，那么整个多项式层级将坍缩至$k$层：对任一$i>k$，都有$\Sigma_i^\mathsf{P}=\Sigma_k^\mathsf{P}$。特别的，如果$\mathsf{P}=\mathsf{NP}$，那么多项式谱系将完全坍缩。

所有多项式层级的类别的并集为复杂度类PH。

## 性质

多项式谱系与指数谱系和算术阶层类似，但复杂度更小。

已经确定PH包含于PSPACE，但不确定两者是否相等。这个问题有一个很有用的变体：PH = PSPACE当且仅当二阶逻辑复杂度类不能通过传递闭包运算扩展计算能力。

如果多项式谱系中有任何完备问题，那么它仅有有限个不同的层次。我们知道存在PSPACE完备问题，所以如果PH = PSPACE，PH必然坍缩，因为对任一PSPACE完备问题必然存在整数$k$使得这个问题是$\Sigma_k^\mathsf{P}$完备的。

每个多项式谱系中的复杂度类都包含$\leq_m^p$完备问题（指多项式次多对一规约的完备问题）。而且每个多项式谱系中的复杂度类都对$\leq_m^p$规约封闭，也就是说对于一个多项式谱系中的复杂度类$\mathcal{C}$和一个语言$\mathcal{L}\in \mathcal{C}$，如果$A\leq_m^p\mathcal{L}$，那么$A\in \mathcal{C}$。这两个事实表明如果$K_i$是$\Sigma_i^\mathsf{P}$的完备问题，那么$\Sigma_{i+1}^\mathsf{P}=\mathsf{NP}^{K_i}$，并且$\Pi_{i+1}^\mathsf{P}=\mathsf{coNP}^{K_i}$。比如说$\Sigma_2^\mathsf{P}=\mathsf{NP}^\mathsf{SAT}$。换句话说，如果一个语言是由某个$\mathcal{C}$预言机定义的，那么我们就可以假设它是基于$\mathcal{C}$中的某个完备问题定义的。完备问题这里就相当于对应复杂度类的一个“代表”。

Sipser–Lautemann定理说明BPP包含于多项式谱系中的第二层。

Kannan定理说明对于任意$k$，$\Sigma_2$都不包含于$\mathsf{SIZE}(n^k)$。

户田定理说明PH包含于$\mathsf{P}^\mathsf{\#P}$。

## 多项式谱系中的问题

- 电路最小化是$\Sigma_2^\mathsf{P}$中的一个自然问题。给定数字$k$和计算布尔函数$f$的电路$A$，判定是否存在能够计算$f$并且至多$k$个门的电路。令$\mathcal{C}$为所有布尔电路的集合。令$G(f)$为计算$f$门数的函数。则语言

$$L = \{\langle A,k,B,x\rangle \in \mathcal{C}\times \mathbb{N}\times \mathcal{C}\times \{0, 1\}^* | G(B)\leq k\wedge A = B\}$$

可在多项式时间内确定。语言

$$CM = \{\langle A, k\rangle \in \mathcal{C}\times \mathbb{N} | \exists B\in \mathcal{C}\wedge G(B)\leq k\wedge A = B\}$$

为最小化电路语言。$CM\in \Sigma_2^\mathsf{P}(=\exists^\mathsf{P}\forall^\mathsf{P}\mathsf{P})$因为$L$在多项式时间内可判定，并且给定$\langle A,k\rangle$，$\langle A,k\rangle\in CM$当且仅当存在电路$B$使得对于所有输入$x$，$\langle A, k, B, x\rangle\in L$。

- 一个$\Sigma_k^\mathsf{P}$完备问题是有$k$量词交替的布尔公式的可满足性（缩写为QBFk或者QSATk）。这是$\Sigma_k^\mathsf{P}$版本的布尔可满足性问题。在这个问题中布尔公式$f$的变量被分成了$k$个集合$X_1, X_2,\dots X_k$。我们需要确定

$$\exists X_1\forall X_2\exists X_3\dots f$$

是否为真。也就是说存在对$X_1$的赋值，使得对所有的$X_2$, 存在对$X_3$的赋值，……，使得$f$为真。从全称量词开始交替到存在量词再到全称量词的变体则是$\Pi_k^\mathsf{P}$完备的。

- 这份 概要包含一份M.R.加里/D.S.约翰逊样式的二阶或更高阶的完备问题清单。