PH (복잡도)

계산 복잡도 이론에서 복잡도 종류 PH는 다항 계층에 있는 모든 복잡도 종류의 합집합이다.

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

PH는 래리 스톡마이어(Larry Stockmeyer)가 처음 정의하였다. 이 복잡도 종류는 PP 신탁 기계에 접근하는 다항 시간 튜링 기계를 써서 판정할 수 있는 문제인 P^PP에 속한다. 토다 정리에 따르면 P^#P에 속하기도 한다. 그리고 PSPACE에도 속한다.

PH는 이차 논리로 표현할 수 있는 언어의 집합이라는 간단한 논리적 특징이 있다.

PH는 PSPACE에 속하는 것 중에서 잘 알려진 복잡도 종류를 거의 모두 포함한다. 여기에는 P, NP, co-NP 따위도 들어가고, 확률적 복잡도 종류인 BPP나 RP도 들어간다.

${\displaystyle {\mbox{P}}={\mbox{NP}}\iff {\mbox{P}}={\mbox{PH}}}$

이것은 P ≠ NP라면 그 증명을 쉽게 하는 데 쓸 수 있다. P를 더 일반적인 종류인 PH에서 분리하기만 하면 되기 때문이다.

• L. J. Stockmeyer, "The polynomial hierarchy", Theoretical Computer Science, Vol. 3 (1976), pp. 1–22.
• (영어) 복잡도 동물원: PH

이 글은 컴퓨터 과학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다.