定义 多项式谱系有数个等价的定义。
用预言机定义多项式谱系。首先定义 Δ 0 P := Σ 0 P := Π 0 P := P , {\displaystyle \Delta _{0}^{\mathsf {P}}:=\Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}},} 其中P 是能在多项式时间 内解决的决定性问题 。然后对所有 i ≥ 0 {\displaystyle i\geq 0} 定义
Δ i + 1 P := P Σ i P {\displaystyle \Delta _{i+1}^{\mathsf {P}}:={\mathsf {P}}^{\Sigma _{i}^{\mathsf {P}}}} Σ i + 1 P := N P Σ i P {\displaystyle \Sigma _{i+1}^{\mathsf {P}}:={\mathsf {NP}}^{\Sigma _{i}^{\mathsf {P}}}} Π i + 1 P := c o N P Π i P {\displaystyle \Pi _{i+1}^{\mathsf {P}}:={\mathsf {coNP}}^{\Pi _{i}^{\mathsf {P}}}} 其中 P A {\displaystyle {\mathsf {P}}^{\rm {A}}} 是在有 A {\displaystyle {\rm {A}}} 类中某些完备问题 的预言机 辅助的情况下,能在多项式时间内由图灵机 解决的决定性问题 的集合。类别 N P A {\displaystyle {\mathsf {NP}}^{\rm {A}}} 和 c o N P A {\displaystyle {\mathsf {coNP}}^{\rm {A}}} 也有类似的定义。比如, Σ 1 P = N P {\displaystyle \Sigma _{1}^{\mathsf {P}}={\mathsf {NP}}} 、 Π 1 P = c o N P {\displaystyle \Pi _{1}^{\mathsf {P}}={\mathsf {coNP}}} 和 Δ 2 P = P N P {\displaystyle \Delta _{2}^{\mathsf {P}}={\mathsf {P^{NP}}}} 是一些能在某些NP完全 问题预言机的辅助下,在多项式时间内解决的问题的复杂度类。[1] 用存在状态或者全称状态定义多项式谱系。令 L {\displaystyle L} 为一个语言(或称为决定性问题,即 { 0 , 1 } ∗ {\displaystyle \{0,1\}^{*}} 的某个子集), p {\displaystyle p} 为某多项式,定义 ∃ p L := { x ∈ { 0 , 1 } ∗ | ( ∃ w ∈ { 0 , 1 } ≤ p ( | x | ) ) ⟨ x , w ⟩ ∈ L } , {\displaystyle \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\},} 其中 ⟨ x , w ⟩ ∈ { 0 , 1 } ∗ {\displaystyle \langle x,w\rangle \in \{0,1\}^{*}} 为某种将二进制字符串对 x {\displaystyle x} 和 w {\displaystyle w} 编码为一个二进制字符串的标准编码。 L {\displaystyle L} 代表一个有序的字符串对的集合,其中第一个字符串x 是 ∃ p L {\displaystyle \exists ^{p}L} 的元素,而第二个字符串 w {\displaystyle w} 是一个足够短的(长度不大于 p ( | x | ) {\displaystyle p(|x|)} )见证 x {\displaystyle x} 在 ∃ p L {\displaystyle \exists ^{p}L} 内的字符串。换句话说, x ∈ ∃ p L {\displaystyle x\in \exists ^{p}L} 当且仅当存在足够短的见证字符串 w {\displaystyle w} 使得 ⟨ x , w ⟩ ∈ L {\displaystyle \langle x,w\rangle \in L} 。类似地,定义 ∀ p L := { x ∈ { 0 , 1 } ∗ | ( ∀ w ∈ { 0 , 1 } ≤ p ( | x | ) ) ⟨ x , w ⟩ ∈ L } {\displaystyle \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\}} 注意到由德摩根定律 得出 ( ∃ p L ) c = ∀ p L c {\displaystyle \left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}} and ( ∀ p L ) c = ∃ p L c {\displaystyle \left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}} ,其中 L c {\displaystyle L^{c}} 是 L {\displaystyle L} 的补集。令 C {\displaystyle {\mathcal {C}}} 为一个语言集。延伸这些运算使得它们能够应用于语言集上: ∃ P C := { ∃ p L | p ∈ P , L ∈ C } {\displaystyle \exists ^{\mathsf {P}}{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p\in {\mathcal {P}},L\in {\mathcal {C}}\right\}} ∀ P C := { ∀ p L | p ∈ P , L ∈ C } {\displaystyle \forall ^{\mathsf {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p\in {\mathcal {P}},L\in {\mathcal {C}}\right\}} 其中 P {\displaystyle {\mathcal {P}}} 为所有多项式的集合。同样德摩根定律成立 c o ∃ P C = ∀ P c o C {\displaystyle {\mathsf {co}}\exists ^{\mathsf {P}}{\mathcal {C}}=\forall ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}} 以及 c o ∀ P C = ∃ P c o C {\displaystyle {\mathsf {co}}\forall ^{\mathsf {P}}{\mathcal {C}}=\exists ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}} ,其中 c o C = { L c | L ∈ C } {\displaystyle {\mathsf {co}}{\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}} 。复杂度类NP和反NP可被定义为 N P = ∃ P P {\displaystyle {\mathsf {NP}}=\exists ^{\mathsf {P}}{\mathsf {P}}} 和 c o N P = ∀ P P {\displaystyle {\mathsf {coNP}}=\forall ^{\mathsf {P}}{\mathsf {P}}} , 其中P是所有可行的(多项式时间内的)递归语言。则多项式谱系可被递归定义为 Σ 0 P := Π 0 P := P {\displaystyle \Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}}} Σ k + 1 P := ∃ P Π k P {\displaystyle \Sigma _{k+1}^{\mathsf {P}}:=\exists ^{\mathsf {P}}\Pi _{k}^{\mathsf {P}}} Π k + 1 P := ∀ P Σ k P {\displaystyle \Pi _{k+1}^{\mathsf {P}}:=\forall ^{\mathsf {P}}\Sigma _{k}^{\mathsf {P}}} 注意 N P = Σ 1 P {\displaystyle {\mathsf {NP}}=\Sigma _{1}^{\mathsf {P}}} , and c o N P = Π 1 P {\displaystyle {\mathsf {coNP}}=\Pi _{1}^{\mathsf {P}}} 。这个定义反映出多项式谱系和算数阶层之间的紧密关系。其中R 和RE 分别扮演了类似P 和NP 的角色。算数阶层同样是用一系列的实数子集来定义的。 用交替式图灵机 的等价定义。定义 Σ k P {\displaystyle \Sigma _{k}^{\mathsf {P}}} (或 Π k P {\displaystyle \Pi _{k}^{\mathsf {P}}} )为从存在状态(或全称状态)开始的 k {\displaystyle k} 次交替式图灵机能够解决的问题的集合。 多项式谱系类别之间的关系 性质 多项式谱系中的问题 电路最小化是 Σ 2 P {\displaystyle \Sigma _{2}^{\mathsf {P}}} 中的一个自然问题。给定数字 k {\displaystyle k} 和计算布尔函数 f {\displaystyle f} 的电路 A {\displaystyle A} ,判定是否存在能够计算 f {\displaystyle f} 并且至多 k {\displaystyle k} 个门的电路。令 C {\displaystyle {\mathcal {C}}} 为所有布尔电路的集合。令 G ( f ) {\displaystyle G(f)} 为计算 f {\displaystyle f} 门数的函数。则语言 L = { ⟨ A , k , B , x ⟩ ∈ C × N × C × { 0 , 1 } ∗ | G ( B ) ≤ k ∧ A = B } {\displaystyle 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\}} 可在多项式时间内确定。语言
C M = { ⟨ A , k ⟩ ∈ C × N | ∃ B ∈ C ∧ G ( B ) ≤ k ∧ A = B } {\displaystyle CM=\{\langle A,k\rangle \in {\mathcal {C}}\times \mathbb {N} |\exists B\in {\mathcal {C}}\wedge G(B)\leq k\wedge A=B\}} 为最小化电路语言。 C M ∈ Σ 2 P ( = ∃ P ∀ P P ) {\displaystyle CM\in \Sigma _{2}^{\mathsf {P}}(=\exists ^{\mathsf {P}}\forall ^{\mathsf {P}}{\mathsf {P}})} 因为 L {\displaystyle L} 在多项式时间内可判定,并且给定 ⟨ A , k ⟩ {\displaystyle \langle A,k\rangle } , ⟨ A , k ⟩ ∈ C M {\displaystyle \langle A,k\rangle \in CM} 当且仅当存在 电路 B {\displaystyle B} 使得对于所有 输入 x {\displaystyle x} , ⟨ A , k , B , x ⟩ ∈ L {\displaystyle \langle A,k,B,x\rangle \in L} 。
一个 Σ k P {\displaystyle \Sigma _{k}^{\mathsf {P}}} 完备问题是有 k {\displaystyle k} 量词交替的布尔公式的可满足性(缩写为QBFk 或者QSATk )。这是 Σ k P {\displaystyle \Sigma _{k}^{\mathsf {P}}} 版本的布尔可满足性问题。在这个问题中布尔公式 f {\displaystyle f} 的变量被分成了 k {\displaystyle k} 个集合 X 1 , X 2 , … X k {\displaystyle X_{1},X_{2},\dots X_{k}} 。我们需要确定 ∃ X 1 ∀ X 2 ∃ X 3 … f {\displaystyle \exists X_{1}\forall X_{2}\exists X_{3}\dots f} 是否为真。也就是说存在对 X 1 {\displaystyle X_{1}} 的赋值,使得对所有的 X 2 {\displaystyle X_{2}} , 存在对 X 3 {\displaystyle X_{3}} 的赋值,……,使得 f {\displaystyle f} 为真。从全称量词 开始交替到存在量词 再到全称量词的变体则是 Π k P {\displaystyle \Pi _{k}^{\mathsf {P}}} 完备的。
另见 参考文献 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. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. 1979. ISBN 0-7167-1045-5 . Section 7.2: The Polynomial Hierarchy, pp. 161–167.引用