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


주요 복잡도 종류 (더 보기)

P | NP | co-NP | NP-C | co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C
EXPTIME | EXPSPACE | PR | RE | co-RE | RE-C | co-RE-C | R | BQP | BPP | RP | ZPP | PCP | IP | PH

이 문서는 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.