PP (복잡도)

[alt=무작위 복잡도 종류 다이어그램|섬네일|upright=1.25|다른 확률적 복잡도 종류([ZPP (complexity)|ZPP, RP, co-RP, BPP, BQP)와 관련된 PP, 이는 PSPACE 내에서 P를 일반화한다. 이러한 포함 관계가 엄격한지는 알려져 있지 않다.]]

복잡도 이론에서 **PP** 또는 **PPT**는 모든 인스턴스에 대해 오차 확률이 1/2 미만으로 다항 시간에 확률적 튜링 기계로 해결 가능한 결정 문제의 종류이다. 약어 **PP**는 확률적 다항 시간을 의미한다. 이 복잡도 종류는 길(Gill)이 1977년에 정의했다.

결정 문제가 **PP**에 속한다면, 확률적 결정을 내릴 수 있는 다항 시간 실행 알고리즘이 존재하며, 이 알고리즘은 1/2보다 높은 확률로 올바른 답을 반환한다. 좀 더 실용적인 용어로 설명하면, 이 종류는 무작위 다항 시간 알고리즘을 충분한(그러나 유한한) 횟수만큼 실행함으로써 어떤 고정된 정확도까지 해결할 수 있는 문제들의 종류이다.

다항적으로 제한된 확률적 튜링 기계는 확률적 다항 시간 기계를 나타내는 **PPT**로 특징지어진다. 이 튜링 기계의 특징은 유한한 오차 확률을 요구하지 않는다. 따라서 **PP**는 오차 확률이 1/2 미만인 PPT 기계로 해결할 수 있는 모든 문제를 포함하는 복잡도 종류이다.

**PP**의 대안적인 특징은 다항 시간 내에 비결정론적 튜링 기계로 해결할 수 있는 문제들의 집합으로, 수용 조건은 계산 경로의 과반수(절반 이상)가 수용하는 것이다. 이 때문에 일부 저자들은 대체 이름으로 Majority-P를 제안했다.

## 정의
언어 L이 **PP**에 속하는 경우는 다음과 같은 확률적 튜링 기계 M이 존재하는 경우에 한한다.
* M은 모든 입력에 대해 다항 시간으로 실행된다.
* L에 있는 모든 x에 대해 M은 1/2 이상의 확률로 1을 출력한다.
* L에 없는 모든 x에 대해 M은 1/2 미만의 확률로 1을 출력한다.

다른 방법으로, **PP**는 결정론적 튜링 기계만을 사용하여 정의할 수 있다. 언어 L이 **PP**에 속하는 경우는 다음과 같은 다항식 p와 결정론적 튜링 기계 M이 존재하는 경우에 한한다.
* M은 모든 입력에 대해 다항 시간으로 실행된다.
* L에 있는 모든 x에 대해 M(x,y) = 1을 만족하는 길이 p(|x|)의 문자열 y의 비율이 1/2보다 크다.
* L에 없는 모든 x에 대해 M(x,y) = 1을 만족하는 길이 p(|x|)의 문자열 y의 비율이 1/2보다 작다.

이 정의에서 문자열 y는 확률적 튜링 기계가 수행했을 무작위 동전 던지기의 결과에 해당한다.

두 정의 모두에서, "미만"은 "이하"로 변경될 수 있고(아래 참조), 임계값 1/2은 (0,1) 범위의 어떤 고정된 유리수로 대체될 수 있으며, 이는 종류를 변경하지 않는다.

## PP 대 BPP
**[[BPP (복잡도)|BPP]]**는 **PP**의 부분집합이다. 이는 효율적인 확률적 알고리즘이 존재하는 부분집합으로 볼 수 있다. 차이점은 허용되는 오차 확률에 있다. **BPP**에서는 알고리즘이 2/3 또는 1000분의 501과 같은 1/2보다 큰 고정 상수 c를 초과하는 확률로 올바른 답(예 또는 아니요)을 제공해야 한다. 이 경우, 체르노프 경계를 사용하여 알고리즘을 여러 번 실행하고 다수결을 통해 1 미만의 원하는 정확도 확률을 달성할 수 있다. 이 반복 횟수는 c가 1/2에 가까워질수록 증가하지만, 입력 크기 n에는 의존하지 않는다.

더 일반적으로, c가 입력 크기 n에 다항적으로, 즉 c = O(n^{-k}) 와 같이 의존할 수 있다면, 알고리즘을 O(n^{2k})번 재실행하고 다수결을 취할 수 있다. 호프딩 부등식에 의해, 이는 우리에게 **BPP** 알고리즘을 제공한다.

중요한 점은 이 상수 c가 입력에 의존하도록 허용되지 않는다는 것이다. 반면에, **PP** 알고리즘은 다음과 같은 작업을 수행할 수 있다.
* YES 인스턴스의 경우, 입력 길이 n에 대해 1/2 + 1/2n의 확률로 YES를 출력한다.
* NO 인스턴스의 경우, 1/2 - 1/2n의 확률로 YES를 출력한다.

이 두 확률은 지수적으로 매우 가깝기 때문에, 다항 시간 동안 실행하더라도 우리가 YES 인스턴스에서 작동하고 있는지 NO 인스턴스에서 작동하고 있는지 구분하기가 매우 어렵다. 다수결과 체르노프 경계를 사용하여 고정된 원하는 확률 수준을 달성하려고 시도하면 n에 대해 지수적인 반복 횟수가 필요하다.

## 다른 복잡도 종류와 PP 비교

**PP**는 **[[BPP (복잡도)|BPP]]**를 포함하는데, **BPP**의 정의에 기술된 확률적 알고리즘이 **PP**의 정의에 있는 알고리즘들의 부분집합을 형성하기 때문이다.

**PP**는 또한 **[[NP (복잡도)|NP]]**를 포함한다. 이를 증명하기 위해, NP-완전인 충족 가능성 문제가 **PP**에 속함을 보인다. 공식 F(x1, x2, ..., xn)가 주어졌을 때, 할당 x1, x2, ..., xn을 균일하게 무작위로 선택하는 확률적 알고리즘을 고려해보자. 그런 다음, 이 알고리즘은 할당이 공식 F를 참으로 만드는지 확인한다. 만약 참이라면 YES를 출력한다. 그렇지 않으면 1/2 - 1/2n + 1의 확률로 YES를 출력하고 1/2 + 1/2n + 1의 확률로 NO를 출력한다.

만약 공식이 충족 불가능하다면, 알고리즘은 항상 1/2 - 1/2n + 1 \left(\frac12 - \frac1{2^{n + 1}}\right)\cdot \left(1 - \frac1{2^n}\right) + 1\cdot\frac1{2^n} = \frac12 + \frac1{2^{2n + 1}} > \frac12
(불충족 할당을 선택한 경우 정확히 1/2이고, 충족 할당을 선택한 경우 1이며, 평균적으로 1/2보다 큰 어떤 숫자). 따라서 이 알고리즘은 충족 가능성을 **PP**에 포함시킨다. **SAT**는 NP-완전이므로, 우리는 어떤 결정론적 다항 시간 다대일 환산도 **PP** 알고리즘에 접두어로 붙일 수 있으므로, **NP**는 **PP**에 포함된다. **PP**는 여집합에 대해 닫혀 있으므로, **co-NP**도 포함한다.

또한 **PP**는 앞의 두 포함 관계를 포함하는 **[[아서-멀린 프로토콜|MA]]**를 포함한다.

**PP**는 효율적인 다항 시간 양자 컴퓨터로 해결 가능한 결정 문제의 종류인 **[[BQP]]**도 포함한다. 사실 BQP는 **PP**에 대해 low인데, 이는 **PP** 기계가 **BQP** 문제를 즉시 해결할 수 있는 능력을 통해 어떤 이점도 얻지 못한다는 것을 의미한다. 후선택이 있는 양자 컴퓨터의 다항 시간 클래스인 **[[PostBQP]]**는 **PP**와 동일하다. (아래 #PostBQP 참조).

더 나아가, **PP**는 **MA**와 **BQP**의 포함을 포함하는 **[[QMA]]**를 포함한다.

PP 오라클을 가진 다항 시간 튜링 기계(**P<sup>PP</sup>**)는 전체 다항 계층인 **[[PH (복잡도)|PH]]**의 모든 문제를 해결할 수 있다. 이 결과는 1989년 토다 세이노스케에 의해 증명되었으며, 토다 정리로 알려져 있다. 이는 **PP**의 문제를 해결하는 것이 얼마나 어려운지에 대한 증거이다. #P 클래스는 **P****#P** = **P<sup>PP</sup>** 이고 따라서 **P****#P**도 **PH**를 포함하므로, 어떤 의미에서는 그만큼 어렵다.

**PP**는 상수 깊이, 무제한 팬인 불 회로와 균일한(다항 시간 알고리즘으로 생성되는) 다수결 게이트를 가진 종류인 균일 **[[TC0|TC<sup>0</sup>]]**를 엄격하게 포함한다.

**PP**는 **[[PSPACE]]**에 포함된다. 이는 아래에 정의된 **MAJSAT**에 대한 다항 공간 알고리즘을 제시함으로써 쉽게 보일 수 있다. 단순히 모든 할당을 시도하고 만족하는 것들의 수를 세면 된다.

**PP**는 칸난 정리에 의해 어떤 k에 대해서도 **SIZE**(nk)에 포함되지 않는다.

## 완전 문제 및 기타 속성
**[[BPP (복잡도)|BPP]]**와 달리, **PP**는 의미론적 종류가 아닌 구문론적 종류이다. 어떤 다항 시간 확률적 기계도 **PP**에 속하는 어떤 언어를 인식한다. 반대로, 다항 시간 확률적 기계의 설명이 주어졌을 때, 그것이 **BPP**에 속하는 언어를 인식하는지 여부를 결정하는 것은 일반적으로 결정 불가능하다.

**PP**에는 자연스러운 완전 문제들이 있는데, 예를 들어 **MAJSAT**이 있다. **MAJSAT**은 불리언 공식 F가 주어졌을 때, 모든 할당 x1, x2, ..., xn 중 절반 이상이 F를 참으로 만드는 경우 YES를, 그렇지 않은 경우 NO를 답해야 하는 결정 문제이다.

### PP가 여집합에 대해 닫혀 있다는 증명
L을 **PP**에 속하는 언어라고 하자. L^c를 L의 여집합이라고 하자. **PP**의 정의에 의해 다음과 같은 속성을 가진 다항 시간 확률적 알고리즘 A가 존재한다.

:x \in L \Rightarrow \Pr[A \text{ accepts } x] > \frac{1}{2} \quad \text{and} \quad x \not\in L \Rightarrow \Pr[A \text{ accepts } x] \le \frac{1}{2}.

우리는 일반성을 잃지 않고, 후자의 부등식이 항상 엄격하다고 주장한다. 정리는 이 주장으로부터 추론될 수 있다: A가 거부하는 경우 A^c는 수용하고 그 반대인 기계인 A^c를 정의하자. 그러면

:x \in L^c \Rightarrow \Pr[A^c \text{ accepts } x] > \frac{1}{2} \quad \text{and} \quad x \not\in L^c \Rightarrow \Pr[A^c \text{ accepts } x] 

이는 L^c가 **PP**에 속함을 의미한다.

이제 일반성을 잃지 않고 가정을 정당화한다. f(|x|)를 입력 x에 대한 A의 실행 시간의 다항 상한이라고 하자. 따라서 A는 실행 중 최대 f(|x|)개의 무작위 동전 던지기를 수행한다. 특히 수용 확률은 2^{-f(|x|)}의 정수배이며 다음과 같다.

:x \in L \Rightarrow \Pr[A \text{ accepts } x] \ge \frac{1}{2} + \frac{1}{2^{f(|x|)}}.

기계 A′를 다음과 같이 정의한다. 입력 x에 대해 A′는 A를 서브루틴으로 실행하고, A가 거부하면 거부한다. 그렇지 않고 A가 수용하면 A′는 f(|x|)+1개의 동전을 던지고, 모두 앞면이면 거부하고, 그렇지 않으면 수용한다. 그러면

:x \not\in L \Rightarrow \Pr[A' \text{ accepts } x] \le \frac{1}{2} \cdot \left (1- \frac{1}{2^{f(|x|)+1}} \right ) 
이고
: x \in L \Rightarrow \Pr[A' \text{ accepts } x] \ge \left (\frac{1}{2}+\frac{1}{2^{f(|x|)}} \right )\cdot \left ( 1-\frac{1}{2^{f(|x|)+1}} \right ) > \frac{1}{2}.

이는 가정을 정당화하고(A′는 여전히 다항 시간 확률적 알고리즘이므로) 증명을 완료한다.

데이비드 루소는 1985년 박사 학위 논문에서 **PP**가 대칭차에 대해 닫혀 있음을 증명했다. **PP**가 합집합과 교집합에 대해 닫혀 있는지 여부는 14년 동안 열린 문제였다. 이는 비겔(Beigel), 라인골드(Reingold), 스필먼(Spielman)에 의해 긍정적으로 해결되었다. 리(Li)와 애런슨(Aaronson)이 나중에 다른 증명을 제시했다(아래 #PostBQP 참조).

## 다른 동등한 복잡도 종류

### PostBQP
양자 복잡도 종류 **[[BQP]]**는 양자 튜링 기계에서 다항 시간에 해결할 수 있는 문제의 종류이다. 후선택을 추가함으로써 더 큰 종류인 **[[PostBQP]]**를 얻을 수 있다. 비공식적으로, 후선택은 컴퓨터에 다음과 같은 능력을 부여한다: 어떤 사건(예: 특정 상태의 큐비트 측정)이 0이 아닌 확률을 가질 때마다, 그것이 발생했다고 가정할 수 있다. 스콧 애런슨은 2004년에 **PostBQP**가 **PP**와 동일하다는 것을 보였다. 이 **PP**의 재정의는 **PP**가 교집합(따라서 합집합)에 대해 닫혀 있다는 것, **BQP**가 **PP**에 대해 low라는 것, 그리고 **[[QMA]]**가 **PP**에 포함된다는 것과 같은 특정 결과를 더 쉽게 보여준다.

### PQP
**PP**는 또한 **[[BQP]]**의 무제한 오차 아날로그로 알려진 또 다른 양자 복잡도 종류인 **PQP**와 동일하다. 이는 모든 인스턴스에 대해 오차 확률이 1/2 미만으로, 다항 시간 내에 양자 컴퓨터로 해결할 수 있는 결정 문제의 종류를 나타낸다. **PQP** 계산에 사용되는 모든 진폭이 대수적 수에서 파생된 경우에도 **PQP**는 **PP**와 일치한다.

## 내용주

## 각주
*.
*.
*

## 외부 링크
* 

분류:확률적 복잡도 종류