PH (복잡도)
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서 복잡도 종류 PH는 다항 계층에 있는 모든 복잡도 종류의 합집합이다.
PH는 래리 스톡마이어(Larry Stockmeyer)가 처음 정의하였다. 이 복잡도 종류는 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
|
|
|---|
| 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 |
 |
이 문서는 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |
