多項式譜系

計算複雜度理論中，多項式譜系是一個複雜度系列。它從P、NP和反NP複雜度類逐級產生至預言機。它類似於數理邏輯中算數階層和分析階層，只不過是由逐級放寬資源限制而產生的。

定義

多項式譜系有數個等價的定義。

1. 用預言機定義多項式譜系。首先定義

   $\Delta _{0}^{\mathsf {P}}:=\Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}},$

   其中P是能在多項式時間內解決的決定性問題。然後對所有$i\geq 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}}^{\Pi _{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$代表一個有序的字符串對的集合，其中第一個字符串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的角色。算數階層同樣是用一系列的實數子集來定義的。
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}}$中的某個完備問題定義的。完備問題這裏就相當於對應複雜度類的一個「代表」。

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$量詞交替的布爾公式的可滿足性（縮寫為QBF_k或者QSAT_k）。這是$\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
• 指數譜系
• 算術階層

參考文獻

1. 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.
2. L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, vol.3, pp. 1–22, 1976.
3. C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Chapter 17. Polynomial hierarchy, pp. 409–438.
4. 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.