PH (복잡도)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

PH는 계산 복잡도 이론에서 다루는 복잡도 클래스로, P, NP, co-NP를 포함하며 PSPACE 내의 거의 모든 잘 알려진 복잡도 클래스를 포함한다. BPP, RP와 같은 확률적 클래스도 포함하지만, BQP는 PH에 포함되지 않는다는 증거가 있다. P = NP는 P = PH일 때에만 성립하며, PH는 P^#P = P^PP의 부분집합이고 PSPACE에도 포함된다.

PH (복잡도)

📚 더 읽어볼만한 페이지

복잡도 종류 - P (복잡도)
P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
복잡도 종류 - P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.

1. 개요
2. 다른 복잡도 클래스와의 관계
- 2.1. 확률적 복잡도 클래스
- 2.2. 신탁 기계(Oracle Machine) 관련 복잡도 클래스
3. 예시
4. 참고 문헌

2. 다른 복잡도 클래스와의 관계

PH는 [[PSPACE]] 내의 거의 모든 잘 알려진 복잡도 클래스를 포함하며, 특히 [[P (복잡도)|P]], [[NP (복잡도)|NP]], 그리고 [[co-NP]]를 포함한다.

P = NP는 P = PH일 때에만 성립한다. 이는 P ≠ NP의 잠재적인 증명을 단순화할 수 있는데, P를 더 일반적인 클래스인 PH와 분리하는 것만으로 충분하기 때문이다.

2.1. 확률적 복잡도 클래스

BPP (이는 Sipser–Lautemann 정리이다)와 RP와 같은 확률적 클래스도 포함한다. 그러나, 양자 컴퓨터로 다항 시간 내에 해결 가능한 문제의 클래스인 BQP는 PH에 포함되지 않는다는 증거가 있다.

2.2. 신탁 기계(Oracle Machine) 관련 복잡도 클래스

PH는 Toda의 정리에 의해 P^#P = P^PP의 부분집합이며, 여기서 P^#P 또는 동등하게 P^PP는 #P 또는 PP 오라클에 접근할 수 있는 다항 시간 튜링 기계에 의해 결정 가능한 문제들의 클래스이다. 또한 PH는 PSPACE에도 포함된다.

3. 예시

(내용 없음)

4. 참고 문헌

* 페터 뷔르기세르. (2000). 대수적 복잡성 이론의 완전성과 환원. 알고리즘과 계산수학 7. 베를린: 스프링거 출판사. ISBN 3-540-66752-0. 66쪽.
* Complexity Zoo: PH