多項式譜系

計算複雜度理論中，多項式譜系是一個複雜度系列。它從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.詹森樣式的二階或更高階的完備問題清單。