PH (복잡도)

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

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

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

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

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

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

분류:복잡도 종류