PH (복잡도)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

\mbox{PH} = \bigcup_{k\in\mathbb{N}} \Delta_k\mbox{P}

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

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

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

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

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

참고 문헌[편집]

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