多項式譜系

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

## 定義

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

## 多項式譜系類別之間的關係

由定義可推論出如下關係：

　
: $\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. 詹森樣式的二階或更高階的完備問題清單。

## 另見

* 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.

## 引用