多項式譜系

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

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

:\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完全问题预言机的辅助下，在多项式时间内解决的问题的复杂度类。

|2=用存在状态或者全称状态定义多项式谱系。令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代表一个有序的字符串对的集合，其中第一个字符串是\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的角色。算数阶层同样是用一系列的实数子集来定义的。

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

}}

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

由定义可推论出如下关系：
: \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}中的某个完备问题定义的。完备问题这里就相当于对应复杂度类的一个“代表”。

说明BPP包含于多项式谱系中的第二层。

说明对于任意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量词交替的布尔公式的可满足性（缩写为**QBF<sub>k</sub>**或者**QSAT<sub>k</sub>**）。这是\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.约翰逊样式的二阶或更高阶的完备问题清单。

## 另见
* EXPTIME
* 指数谱系
* 算术阶层

## 参考文献
# A. R. Meyer and L. J. Stockmeyer.  The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space.  *In Proceedings of the 13th IEEE [[Symposium on Switching and Automata Theory]]*, pp.&nbsp;125&ndash;129, 1972.  The paper that introduced the polynomial hierarchy.
# L. J. Stockmeyer. The polynomial-time hierarchy. *Theoretical Computer Science*, vol.3, pp.&nbsp;1&ndash;22, 1976.
# C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Chapter 17. *Polynomial hierarchy*, pp.&nbsp;409&ndash;438.
#  Section 7.2: The Polynomial Hierarchy, pp.&nbsp;161–167.

## 引用