PH (複雜度)

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

${\displaystyle {\mbox{PH}}=\bigcup _{k\in \mathbb {N} }\Delta _{k}{\mbox{P}}}$

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

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

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

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

參考資料

• 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), , Template:ECCC.
• Complexity Zoo: PH