查看“︁PH (複雜度)”︁的源代码

在[[計算複雜度理論]]內，[[複雜度類]]'''PH'''代表所有在[[多項式譜系]]裡面的複雜度類聯集，亦即：

:<math>\mbox{PH} = \bigcup_{k\in\mathbb{N}} \Delta_k\mbox{P}</math>

'''PH'''最早是由[[Larry Stockmeyer]]定義，是一個[[交替式圖靈機|受限交替式圖靈機]](bounded alternating Turing machine)其譜系(hierarchy)的特例。這個複雜度包含於'''P<sup>PP</sup>'''(包含問題可以由多項式時間[[圖靈機]]，並且能取用[[PP (複雜度)|PP]] [[諭示機|神諭]]的機器所解決的複雜度類。), '''P<sup>#P</sup>''' (根據[[Toda's theorem]]),以及'''[[PSPACE]]'''裡面。

'''PH'''有一個簡單的邏輯描述方法：'''PH'''是一個能以[[二階邏輯]]所表示語言的集合。

'''PH'''包含了幾乎所有在'''PSPACE'''裡面有名的複雜度類;舉例來說，像是'''[[P (複雜度)|P]]''', '''[[NP (複雜度)|NP]]'''，和'''[[co-NP]]'''。甚至還包含了一些概率複雜度類像是'''[[BPP (複雜度)|BPP]]'''和'''[[RP (複雜度)|RP]]'''。然而，有一些證據指出'''[[BQP]]'''(以[[量子電腦]]可以在多項式時間之內解決的問題)並不包含在'''PH'''裡面(Aaronson 2010). 

'''P''' = '''NP'''若且唯若'''P''' = '''PH'''。這可能是一個比較簡單證明'''P''' &ne; '''NP'''的方式，因為我們只要把'''P'''從比較廣義的 '''PH'''分別出來即可。

==參考資料==
{{refbegin}}
*[[Larry J. Stockmeyer]], "The polynomial hierarchy", ''Theoretical Computer Science'', Vol. 3 (1976), pp. 1–22.
*[[Scott Aaronson]], BQP and the Polynomial Hierarchy, ACM [[STOC]] (2010), {{arxiv|0910.4698}}, {{ECCC|2009|09|104}}.
*{{CZoo|PH|P#ph}}
{{refend}}

{{複雜度類}}

[[Category:複雜度類]]