多項式階層（polynomial hierarchy）
NP 捕捉的是帶一層「存在」的問題（是否存在一個見證？），co-NP 捕捉的是一層「對所有」（是否每個候選都通過？）。多項式階層就是把這些量詞以交錯的層層疊起所得：存在 ... 對所有 ... 存在 ...，每一層翻轉量詞。它是緊鄰 NP 與 co-NP 上方的困難度精細結構，一座每層都比前一層略強的類別之塔，坐落在 NP 與 PSPACE 之間。
形式上，這個階層的層級命名為 Sigma_k 與 Pi_k（Sigma 是希臘大寫 S，Pi 是希臘大寫 P）。Sigma_1 是 NP（一塊存在量詞），Pi_1 是 co-NP（一塊對所有量詞）。Sigma_2 問題能以「存在 u，對所有 v，predicate(x,u,v)」驗證，其中 u 與 v 為多項式長度、述詞可在多項式時間檢查；Pi_2 把領頭量詞換成「對所有 u，存在 v ...」。一般而言 Sigma_k 允許 k 塊交錯量詞、以存在開頭，Pi_k 以對所有開頭。整個階層 PH 是所有這些層級的聯集。一個等價而優雅的觀點用神諭機：Sigma_(k+1) 是帶有一個 Sigma_k 完全問題神諭的 NP，靠免費諮詢下一層的能力往上爬一階。
PH 是 NP 與 PSPACE 之間地帶的精細地圖：NP 與 co-NP 都坐在第 1 層，整個階層包含於 PSPACE（封頂交錯次數就仍待在多項式空間；移除上限就透過 TQBF 得到整個 PSPACE）。其定義性的信念是這個階層嚴格且無窮：每一層都被猜測嚴格大於下一層，所以它不塌縮。但一如慣例，這仍未解。一個著名的條件性事實把它繫於 P 對 NP：若 P 等於 NP，整個階層就塌縮到 P；更一般地說，若任兩個相鄰層級重合，它們上方的一切都塌縮到那一層。提醒：PH 的塌縮被認為極不可能，這也是研究者相信 P 不是 NP 的標準理由之一。
一個 Sigma_2 問題：給定一個布林公式，是否存在一個大小 <= k 的最小等價公式？這天然就是「存在一個大小 <= k 的公式 psi，使得對所有指派，psi 與 phi 一致」。領頭的存在、接著對所有，共兩次交錯，把它放在階層的第 2 層，很可能在 NP 之上。
多項式階層把交錯的存在/對所有量詞疊起；第 1 層是 NP 與 co-NP，整體都在 PSPACE 之內。
這個階層被「相信」是無窮且嚴格的，但那仍未解。一個關鍵的條件性事實：若 P = NP（或任兩相鄰層級重合），整個階層就塌縮。這樣的塌縮被認為極不可能。