計算複雜度理論中,多項式譜系是一個複雜度系列。它從P、NP和反NP複雜度類逐級產生至預言機。它類似於數理邏輯中算數階層和分析階層,只不過是由逐級放寬資源限制而產生的。
多項式譜系有數個等價的定義。
- 用預言機定義多項式譜系。首先定義
其中P是能在多項式時間內解決的決定性問題。然後對所有定義
其中是在有類中某些完備問題的預言機輔助的情況下,能在多項式時間內由圖靈機解決的決定性問題的集合。類別和也有類似的定義。比如,、 和是一些能在某些NP完全問題預言機的輔助下,在多項式時間內解決的問題的複雜度類。[1] - 用存在狀態或者全稱狀態定義多項式譜系。令為一個語言(或稱為決定性問題,即的某個子集),為某多項式,定義
其中為某種將二進制字符串對和編碼為一個二進制字符串的標準編碼。代表一個有序的字符串對的集合,其中第一個字符串x是的元素,而第二個字符串是一個足夠短的(長度不大於)見證在內的字符串。換句話說,若且唯若存在足夠短的見證字符串使得。類似地,定義
注意到由德摩根定律得出 and ,其中是的補集。令為一個語言集。延伸這些運算使得它們能夠應用於語言集上:
其中為所有多項式的集合。同樣德摩根定律成立以及,其中。
複雜度類NP和反NP可被定義為和, 其中P是所有可行的(多項式時間內的)遞歸語言。則多項式譜系可被遞歸定義為
注意, and 。這個定義反映出多項式譜系和算數階層之間的緊密關係。其中R和RE分別扮演了類似P和NP的角色。算數階層同樣是用一系列的實數子集來定義的。 - 用交替式圖靈機的等價定義。定義(或)為從存在狀態(或全稱狀態)開始的次交替式圖靈機能夠解決的問題的集合。
- 電路最小化是中的一個自然問題。給定數字和計算布爾函數的電路,判定是否存在能夠計算並且至多個門的電路。令為所有布爾電路的集合。令為計算門數的函數。則語言
可在多項式時間內確定。語言
為最小化電路語言。因為在多項式時間內可判定,並且給定,若且唯若存在電路使得對於所有輸入,。
- 一個完備問題是有量詞交替的布爾公式的可滿足性(縮寫為QBFk或者QSATk)。這是版本的布爾可滿足性問題。在這個問題中布爾公式的變量被分成了個集合。我們需要確定
是否為真。也就是說存在對的賦值,使得對所有的, 存在對的賦值,……,使得為真。從全稱量詞開始交替到存在量詞再到全稱量詞的變體則是完備的。
- 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.
Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans