PP (복잡도)

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

PP 알고리즘
생성 된 답변 정답 출력	예	아니요
예	> 1/2	< 1/2
아니요	< 1/2	> 1/2

다른 확률적 복잡도 종류(ZPP, RP, co-RP, BPP, BQP)와 관련된 PP, 이는 PSPACE 내에서 P를 일반화한다. 이러한 포함 관계가 엄격한지는 알려져 있지 않다.

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

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

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

정의

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

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

중요한 점은 이 상수 c가 입력에 의존하도록 허용되지 않는다는 것이다. 반면에, PP 알고리즘은 다음과 같은 작업을 수행할 수 있다.

• YES 인스턴스의 경우, 입력 길이 n에 대해 1/2 + 1/2ⁿ의 확률로 YES를 출력한다.
• NO 인스턴스의 경우, 1/2 - 1/2ⁿ의 확률로 YES를 출력한다.

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

다른 복잡도 종류와 PP 비교

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

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

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

또한 PP는 앞의 두 포함 관계를 포함하는 MA를 포함한다.^[4]

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

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

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

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

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

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

완전 문제 및 기타 속성

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

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

PP가 여집합에 대해 닫혀 있다는 증명

L을 PP에 속하는 언어라고 하자. ${\displaystyle L^{c}}$를 L의 여집합이라고 하자. PP의 정의에 의해 다음과 같은 속성을 가진 다항 시간 확률적 알고리즘 A가 존재한다.

${\displaystyle 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]\leq {\frac {1}{2}}.}$

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

${\displaystyle 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]<{\frac {1}{2}},}$

이는 ${\displaystyle L^{c}}$가 PP에 속함을 의미한다.

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

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

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

${\displaystyle x\not \in L\Rightarrow \Pr[A'{\text{ accepts }}x]\leq {\frac {1}{2}}\cdot \left(1-{\frac {1}{2^{f(|x|)+1}}}\right)<{\frac {1}{2}}}$

이고

${\displaystyle x\in L\Rightarrow \Pr[A'{\text{ accepts }}x]\geq \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년 박사 학위 논문에서^[8] PP가 대칭차에 대해 닫혀 있음을 증명했다. PP가 합집합과 교집합에 대해 닫혀 있는지 여부는 14년 동안 열린 문제였다. 이는 비겔(Beigel), 라인골드(Reingold), 스필먼(Spielman)에 의해 긍정적으로 해결되었다.^[9] 리(Li)^[10]와 애런슨(Aaronson)이 나중에 다른 증명을 제시했다(아래 #PostBQP 참조).

다른 동등한 복잡도 종류

PostBQP

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

PQP

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