다항 위계

계산 복잡도 이론에서 다항 위계(Polynomial hierarchy), 다항 시간 위계는 NP 및 Co-NP 클래스를 일반화하는 위계적인 복잡도 종류이다.Arora and Barak, 2009, pp.97 위계의 각 클래스는 PSPACE 내에 포함된다. 이 위계는 신탁 기계 또는 교대 튜링 기계를 사용하여 정의할 수 있다. 이는 수리 논리학의 산술적 위계 및 해석적 위계에 대한 자원 제약적 대응물이다. 위계 내 클래스의 합집합은 PH로 표기된다.

위계 내의 클래스는 수량자 순서에 대한 제한이 있는 공식에 대해 정량화 부울 공식이 참인지 묻는 완전한 문제(다항 시간 환원과 관련하여)를 가진다. 위계에서 동일한 수준 또는 연속적인 수준의 클래스 간의 등식은 해당 수준으로 위계가 "붕괴"함을 의미한다는 것이 알려져 있다.

정의
다항 위계의 클래스에 대한 여러 동등한 정의가 있다.

신탁 정의
다항 위계의 신탁 정의를 위해 다음을 정의한다.

여기서 P는 다항 시간 내에 해결 가능한 결정 문제들의 집합이다. 그런 다음 i ≥ 0에 대해 다음을 정의한다.

여기서 는 클래스 A의 어떤 완전 문제에 대한 신탁에 의해 다항 시간에 해결 가능한 결정 문제들의 집합이다. 클래스  및 는 유사하게 정의된다. 예를 들어,  이고 는 어떤 NP-완전 문제에 대한 오라클을 가진 결정적 튜링 기계로 다항 시간 안에 해결 가능한 문제들의 클래스이다.Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans

정량화 부울 공식 정의 
다항 위계의 존재/전체 정의를 위해, 을 형식 언어(즉, 결정 문제, {0,1}*의 부분집합)라고 하고, 를 다항식이라고 하자. 그리고 다음을 정의한다.



여기서 는 두 이진 문자열 x와 w를 하나의 이진 문자열로 인코딩하는 표준 방법이다. 언어 L은 문자열의 순서쌍 집합을 나타내며, 첫 번째 문자열 x는 의 멤버이고 두 번째 문자열 w는 x가 의 멤버임을 증명하는 "짧은" () 증거이다. 다시 말해, 인 경우에만 를 만족하는 짧은 증거 w가 존재한다. 비슷하게, 다음을 정의한다.


드 모르간의 법칙이 성립한다:  및 , 여기서 Lc는 L의 여집합이다.

가 언어의 클래스라고 하자. 이러한 연산자를 언어의 전체 클래스에 적용하도록 다음 정의를 통해 확장한다.

다시 말해, 드 모르간의 법칙이 성립한다:  및 , 여기서 이다.

클래스 NP와 Co-NP는 , 그리고 로 정의할 수 있으며, 여기서 P는 모든 실행 가능하게 (다항 시간) 결정 가능한 언어의 클래스이다. 다항 위계는 다음과 같이 재귀적으로 정의할 수 있다.

 및 임을 주목한다.

이 정의는 다항 위계와 산술적 위계 사이의 밀접한 관계를 반영하며, 여기서 R과 RE는 각각 P와 NP에 비유되는 역할을 한다. 해석적 위계 또한 유사한 방식으로 정의되어 실수의 부분 집합 위계를 제공한다.

교대 튜링 기계 정의
교대 튜링 기계는 비최종 상태가 존재 상태와 전체 상태로 분할된 비결정적 튜링 기계이다. 다음 경우에 현재 구성에서 결국 수락한다: 존재 상태에 있고 결국 수락하는 구성으로 전환할 수 있는 경우; 또는, 전체 상태에 있고 모든 전환이 결국 수락하는 구성으로 이어지는 경우; 또는, 수락 상태에 있는 경우.Arora and Barak, pp.99–100

를 다항 시간 내에 교대 튜링 기계에 의해 수락되는 언어의 클래스라고 정의한다. 이 기계는 초기 상태가 존재 상태이고 기계가 취할 수 있는 모든 경로가 존재 상태와 전체 상태 사이를 최대 k – 1번 교환한다. 유사하게, 를 초기 상태가 전체 상태인 경우로 정의한다.Arora and Barak, pp.100

존재 상태와 전체 상태 사이의 최대 k – 1회 교환 요구 사항을 생략하고 교대 튜링 기계가 다항 시간에 실행되기만 요구하는 경우, 클래스 AP의 정의를 가지며, 이는 PSPACE와 같다.Arora and Barak, pp.100

다항 위계 내 클래스 간의 관계
250px|섬네일|right|다항 시간 위계와 동등한 가환 다이어그램. 화살표는 포함 관계를 나타낸다.
다항 위계의 모든 클래스의 합집합은 복잡도 클래스 PH이다.

정의는 다음과 같은 관계를 암시한다.

포함 관계가 참임이 알려진 산술 및 해석적 위계와 달리, 이러한 포함 관계 중 어느 것이 참인지에 대한 질문은 미해결 문제이지만, 모두 참이라고 널리 믿어진다. 만약 어떤 이거나, 어떤 이면, 위계는 k 수준으로 붕괴된다: 모든 에 대해 이다.Arora and Barak, 2009, Theorem 5.4 특히, 미해결 문제와 관련된 다음 함의가 있다.

 P = NP는 P = PH인 경우에만 해당한다.
 만약 NP = Co-NP이면 NP = PH이다. (Co-NP는 이다.)
NP = PH인 경우를 PH가 두 번째 수준으로 붕괴되었다고도 한다. P = NP인 경우는 PH가 P로 붕괴된 것에 해당한다.

첫 번째 수준으로의 붕괴 문제는 일반적으로 매우 어렵다고 생각된다. 대부분의 연구자들은 두 번째 수준으로의 붕괴조차 믿지 않는다.

다른 클래스와의 관계

섬네일|P, NP, Co-NP, BPP, P/poly, PH, 및 PSPACE를 포함한 복잡도 클래스의 하세 도형

다항 위계는 지수 위계와 산술적 위계의 아날로그(훨씬 낮은 복잡도에서)이다.

PH는 PSPACE 내에 포함되어 있지만, 두 클래스가 같은지는 알려져 있지 않다. 이 문제의 유용한 재정식화는 PH = PSPACE인 경우에만 유한 구조에 대한 2차 논리가 관계에 대한 관계(즉, 2차 변수에 대한) 전이 폐포 연산자의 추가로 추가적인 능력을 얻지 못한다는 것이다.

다항 위계에 완전 문제가 있다면, 그것은 유한하게 많은 고유한 수준만을 가진다. PSPACE-완전 문제가 존재하므로, PSPACE = PH라면 다항 위계는 붕괴해야 한다. 왜냐하면 PSPACE-완전 문제는 어떤 k에 대한 -완전 문제가 될 것이기 때문이다.Arora and Barak, 2009, Claim 5.5

다항 위계의 각 클래스는 -완전 문제(다항 시간 다대일 환원에 대한 완전 문제)를 포함한다. 또한, 다항 위계의 각 클래스는 -환원에 대해 닫혀 있다: 즉, 위계 내의 클래스 와 언어 에 대해, 만약 이면 이다. 이 두 가지 사실은 가 에 대한 완전 문제라면, 이고 임을 의미한다. 예를 들어, 이다. 다시 말해, 어떤 언어가 의 어떤 오라클을 기반으로 정의된다면, 그것이 에 대한 완전 문제를 기반으로 정의된다고 가정할 수 있다. 따라서 완전 문제는 그것이 완전한 클래스의 "대표" 역할을 한다.

 십저-라우테만 정리: .
 칸난 정리: . 인지는 미해결 문제이다.
 토다의 정리: .

양자 컴퓨터에 의해 다항 시간 안에 해결 가능한 문제들의 클래스인 BQP가 PH에 포함되지 않는다는 일부 증거가 있다. 그러나 PH가 BQP에 포함되지 않는다고도 믿어진다.=

문제

 같이 보기 
 EXPTIME
 지수 위계
 산술적 위계

 각주 

일반 참조

 A. R. 마이어와 L. J. 스톡마이어. Squaring이 있는 정규 표현식의 등가 문제에는 지수 공간이 필요하다. 제13회 IEEE 스위칭 및 자동화 이론 심포지엄 회의록, pp. 125–129, 1972. 다항 위계를 소개한 논문.
 L. J. 스톡마이어. 다항 시간 위계. 이론 컴퓨터 과학, vol.3, pp. 1–22, 1976.
 C. 파파디미트리우. 계산 복잡도. 애디슨-웨슬리, 1994. 17장. 다항 위계, pp. 409–438.
  7.2절: 다항 위계, pp. 161–167.

인용

분류:복잡도 종류