计算复杂度理论中，多项式谱系是一个复杂度系列。它从P、NP和反NP复杂度类逐级产生至预言机。它类似于数理逻辑中算数阶层和分析阶层，只不过是由逐级放宽资源限制而产生的。
定义
多项式谱系有数个等价的定义。
{{ordered list|
1= 用预言机定义多项式谱系。首先定义
:\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完全问题预言机的辅助下，在多项式时间内解决的问题的复杂度类。
|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。
性质
{{unsolved|计算机科学|{{tmath|1= \mathsf{PH} \overset{?}{=} \mathsf{PSPACE} }}}}
多项式谱系与指数谱系和算术阶层类似，但复杂度更小。
已经确定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量词交替的布尔公式的可满足性（缩写为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}完备的。
- 这份[http://ovid.cs.depaul.edu/documents/phcom.pdf 概要]包含一份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. 125–129, 1972. The paper that introduced the polynomial hierarchy.
L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, vol.3, pp. 1–22, 1976.
C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Chapter 17. Polynomial hierarchy, pp. 409–438.
Section 7.2: The Polynomial Hierarchy, pp. 161–167.
引用
评论 (0)