IP(복잡성)

계산 복잡성 이론에서, 클래스 IP(Interactive Polyomial time을 의미함)는 인터랙티브 증명 시스템으로 해결할 수 있는 문제의 클래스다.그것은 PSPACE 등급과 같다.그 결과는 일련의 논문에서 확립되었다. 첫째는 룬드, 카를로프, 포트노우, 그리고 니산이었다. 첫째는 co-NP가 복수의 프로베스터 인터랙티브 증거를 가지고 있다는 것을 보여주었고,^[1] 둘째는 샤미르에 의해 IP=PSPACE를 확립하기 위해 그들의 기술을 사용했다.^[2]그 결과는 증거가 상대화되지 않는 유명한 예다.^[3]

인터랙티브 증명 시스템의 개념은 1985년 샤피 골드워서, 실비오 미칼리, 찰스 라코프에 의해 처음 도입되었다.쌍방향 증명 시스템은 두 개의 기계, 즉 주어진 문자열 n이 일부 언어의 멤버라는 증거를 제시하는 P와 제시된 증거가 맞는지 확인하는 V로 구성된다.프로베르는 계산과 저장에서 무한하다고 가정하는 반면 검증기는 길이가 n의 크기에서 다항식인 임의 비트 문자열에 접근할 수 있는 확률론적 다항식 시간 기계다.이 두 기계는 다항식 번호인 p(n)를 교환하고 교호작용이 완료되면 검증자는 오류 확률이 1/3밖에 되지 않는 상태에서 n이 언어에 있는지 여부를 결정해야 한다.(그러므로 BPP의 어떤 언어도 IP에 있으므로 검증자는 프로베라를 무시하고 스스로 결정을 내릴 수 있다.)

정의

언어 L은 모든 Q에 대해 다음과 같은 V, P가 존재하는 경우 IP에 속한다.

${\displaystyle w\in L\Rightarrow \Pr[V\왼쪽 화살표 P{\text{{}}가 허용됨 }w]\geq {\tfrac {2}{3}}}}$

${\displaystyle w\\not \in L\Rightarrow \Pr[V\왼쪽 화살표 Q{\text{{}}는 }w]\leq {\tfrac{1}{3}}}}}}$

라슬로 바바이가 도입한 아서-머린 프로토콜은 다항식이 아닌 상수에 의해 교호작용의 횟수가 경계가 되는 것을 제외하고는 성격이 비슷하다.

골드웨서 외검증자가 사용하는 임의의 번호를 도전과 함께 프로베라에게 제공하는 퍼블릭 코인 프로토콜은 프라이빗 코인 프로토콜보다 더 강력하지 않다는 것을 보여주었다.개인-코인 프로토콜의 효과를 복제하려면 최대 두 번의 추가 상호 작용이 필요하다.검증자는 항상 개인 동전 던지기의 결과를 프로베서에게 보낼 수 있기 때문에 반대되는 포함은 간단하다. 이는 두 가지 유형의 프로토콜이 동등하다는 것을 증명한다.

다음 절에서 우리는 전통적인 PSPACE 증명서가 기하급수적으로 길 수도 있지만, 다항식 시간에 문자열이 언어의 구성원인지를 결정하기 위해 대화형 증명 시스템을 사용할 수 있다는 것을 증명한다. 복잡성의 중요한 정리인 IP = PSPACE를 증명한다.

IP 증명 = PSPACE

증명서는 두 부분으로 나눌 수 있는데, 우리는 IP ⊆ PSPACE와 PSPACE ip IP를 보여준다.

IP ⊆ PSPACE

IP ⊆ PSPACE를 증명하기 위해 다항 우주 기계에 의한 쌍방향 증명 시스템의 시뮬레이션을 제시한다.이제 다음을 정의할 수 있다.

${\displaystyle \Pr[V{\text{{}}에서 시작하는 }w{\text{{}}}=\max \nolimits _{P}\Pr \left[V\leftarrow P{\text}}}}}에서 시작하는 }w{{\text{}}}}을 수락한다.$

그리고 매 0 ≤ j ≤ p와 모든 메시지 이력 M에_j 대해 N: 함수를_Mj 귀납적으로 정의한다.

${\displaystyle N_{M_{j}}={\begin{cases}0&j=p{\text{ and }}m_{p}={\text{reject}}\\1&j=p{\text{ and }}m_{p}={\text{accept}}\\\max _{m_{j+1}}N_{M_{j+1}}&j<p{\text{ and }}j{\text{ is odd}}\\{\text{wt-avg}}_{m_{j+1}}N_{M_{j+1}}&j<p{\text{ and }}j{\text{ is even}}\\\end{cases}}}$

여기서:

${\displaystyle {\text{wt-avg}_{m_{j+1}N_{M_{j+1}:{j+1}:{n2}}:=\sum \nolimits _{m_{j+1}\Pr \nolimits _{r}[V(w,r,M_{j}}=m_{j+1}]N_{M_{j+1}}$

여기서 Pr은_r 길이 p의 무작위 문자열 r을 인수할 확률이다.이 식은 검증자가 메시지 m을_j+1 보낸 확률에 의해 가중된 N의_Mj+1 평균이다.

M을₀ 빈 메시지 시퀀스로 지정하면 다항식 공간에서 N을_M0 계산할 수 있으며 N_M0 = Pr[V는 w를 허용함]을 확인할 수 있다.첫째, N을_M0 계산하기 위해 알고리즘은 모든 j와 M에_j 대한 값 N을_Mj 재귀적으로 계산할 수 있다.재귀 깊이는 p이므로 다항식 공간만 있으면 된다.두 번째 요건은 w가 A에 있는지 여부를 결정하는 데 필요한 값인 N_M0 = Pr[V가 w를 수락함]이 필요하다는 것이다.우리는 이것을 증명하기 위해 다음과 같이 유도를 사용한다.

우리는 매 0 ≤ j p p와 매 M에_j 대해_Mj N = Pr[V는 M에서_j 시작하는 w를 받아들인다]라는 것을 보여주어야 하며, 우리는 j에 인덕션을 이용하여 이것을 할 것이다.기본 사례는 j = p에 대해 증명하는 것이다.그럼 인덕션을 이용해서 p에서 0으로 내려갈게.

j = p의 베이스 케이스는 상당히 간단하다.m은_p 수락 또는 거절이므로, m이_p 수락되면 N이_Mp 1로 정의되고 메시지 스트림이 승낙을 나타내므로 Pr[V는 M_j] = 1로 시작하는 것을 허용하므로 클레임이 참이다.m이_p 기각이라면 그 주장은 매우 비슷하다.

귀납 가설의 경우, 일부 j+1 ≤ p와 모든 메시지 순서 M에_j+1 대해 N_Mj+1 = Pr[V는 M]에서_j+1 시작하는 w를 받아들인다. 그리고 나서 j와 모든 메시지 순서 M에_j 대한 가설을 증명한다고 가정한다.

j가 짝수라면 m은_j+1 V에서 P로 보내는 메시지다.N의_Mj 정의에 의하면

${\displaystyle N_{M_{j}}=\sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}\{nolimits _{r_{j}}}=m_{j+1}\right]N_{M_{j+1}.}$

그렇다면 귀납 가설에 의하면, 이것은 와 동등하다고 할 수 있다.

${\displaystyle \sum \nolimits _{m_{j+1}\Pr \nolimits _{r}\{nolimits _{r_{j}}=m_{j+1}\right]\Pr \left[V{\text{{}}는 }{{}M_{j+1}\right]에서 시작하는 }w{\text{}를 수락한다.}$

마지막으로, 정의상 Pr[V는 M에서_j 시작하는 w를 받아들인다]와 같다는 것을 알 수 있다.

j가 이상하면 m은_j+1 P에서 V로 보내는 메시지다.정의상,

${\displaystyle N_{M_{j}}=\max \nolimits_{m_{j+1}N_{M_{j+1}.}$

그렇다면 귀납적 가설로 보면 이것은 동등하다.

${\displaystyle \max \nolimits _{m_{j+1}*\Pr[V{\text{{}}}는(는) }{{j+1}부터 시작하는 }w{\text{}를 수락한다.}$

이는 다음과 같은 이유로 Pr[V가_j M]에서 시작하는 W를 수락한 것과 같다.

${\displaystyle \max \nolimits _{m_{j+1}\Pr[V{\text{{}}}}}에서 시작하는 }w{\text{}}}을(를) 수락함$

왜냐하면 오른쪽의 프로베르는 왼쪽의 표현을 최대화하기 위해 m이라는_j+1 메시지를 보낼 수 있기 때문이다.그리고:

${\displaystyle \max \nolimits _{m_{j+1}1}\Pr \lift[V{\text{{{j+1}\right]\geq \Pr \left[V{\text}}}}}}에서 시작하는 }w{{w{\text{}}}}ligext}}}}}ligext}}}}}}을 수락한다.$

왜냐하면 같은 프로베르는 같은 메시지를 보내는 것보다 더 나은 것을 할 수 없기 때문이다.그러므로, 이것은 내가 짝수인지 홀수인지 여부와 IP ⊆ PSPACE가 완성되었다는 증거를 담고 있다.

여기서 우리는 언어 A에서 특정 문자열 w에 대해 최고의 프로베라 P를 사용하는 다항식 우주 기계를 만들었다.우리는 다항식 공간에서 임의 입력 비트의 모든 집합을 시도할 수 있기 때문에 임의 입력 비트가 있는 프로베롤 대신 이 최고의 프로베러를 사용한다.다항식 우주 기계로 쌍방향 증명 시스템을 시뮬레이션한 이후, IP ⊆ PSPACE를 원하는 대로 보여 주었다.

PSPACE ⊆ IP

PSPACE ⊆ IP를 입증하는 데 사용될 기법을 설명하기 위해 우선 룬드 외 연구진이 입증한 보다 약한 정리를 증명할 것이다.: #SAT ∈ IP.그리고 이 증명서의 개념을 이용하여 TQBF ∈ IP를 보여주기 위해 확장한다.TQBF ∈ PSpace-complete, TQBF ∈ IP 이후 PSPACE ⊆ IP.

#SAT는 IP의 회원이다.

우리는 #SAT가 IP에 있다는 것을 보여줌으로써 시작한다.

${\displaystyle \#{\text{SAT}=\\왼쪽\{\langle \varphi ,k\rangle \ :\\varphi {\text{}는 정확히 }k{\text{충족 할당}\right\}}을(를) 가진 CNF 형식이다.}$

이는 함수가 아닌 의사결정 문제라는 점에서 #SAT의 일반적인 정의와는 다르다는 점에 유의한다.

먼저 산술화를 사용하여 n개의 변수인 ((b₁, ..., b_n)를 가진 부울 공식을_φ 다항₁ p(x_n, ..., x)에 매핑한다_φ. 여기서 p는_φ φ이 참이면_φ 1이고, p의 변수가 부울 값을 할당하면 0이다.φ에서 사용하는 부울 연산 ∨, ∧, ¬은 아래 표와 같이 φ에서 연산자를 교체하여 p에서_φ 시뮬레이션한다.

부울 공식 φ(b₁, ..., b_n)을 다항식 p_φ(x₁, ..., x_n)로 변환하기 위한 산술화 규칙

∧ b	AB
∨ b	a ∗ b := 1 − (1 − a)(1 − b)
¬a	1 − a

예를 들어 φ = ∧ (b ∨ ∨ cc)는 다음과 같이 다항식으로 변환된다.

$\displaystyle {\b*(b*(1-c)\right)\\\\\barphi }&=a\b\bee \neg c)\&=a\nowled.\&=a\cHB \left(1-b)(1-(1-c)\right)\\&=a\왼쪽(1-b)(1-(1-c)\오른쪽)\&=a-(ac-protection)\end{aigned}}$

연산 ab와 a b b는 각각 a와 b의 다항식의 도합에 의해 경계되는 정도를 갖는 다항식을 초래하므로 변수의 정도는 최대 φ의 길이에 있다.

이제 F는 순서 q > 2의ⁿ 유한한 필드가 되게 하고, 또한 q가 적어도 1000이 되도록 요구한다.For each 0 ≤ i ≤ n, define a function f_i on F, having parameters ${\displaystyle a_{1},\dots ,a_{i-1}\in F}$, and a single variable a_i in F: For 0 ≤ i ≤ n and for ${\displaystyle a_{1},\dots ,a_{i}\in F}$ let

${\displaystyle f_{i}(a_{1},\reason,a_{i})=\sum \immits _{a_{i+1},\reason,a_{n}\in \{0,1\}p(a_{1},\n}).}$

f의₀ 값은 φ.f의₀ 만족스러운 할당 수이며 변수가 없는 무효함수라는 점에 유의한다.

이제 #SAT에 대한 프로토콜은 다음과 같이 작동한다.

• 0단계: 프로베라 P는 prime qⁿ > 2를 선택하고₀ f를 계산한 다음, q와₀ f를 검증기 V로 보낸다.V는 q가 max(1000, 2ⁿ)보다 큰 prime이고 f₀() = k인지 점검한다.
• 1단계: P는 다항식으로서₁ f(z)의 계수를 z 단위로 보낸다.V는 f의₁ 정도가 n 이하인지, f₀ = f₁(0) + f₁(1)인지를 확인한다(V가 아닌 경우 거부).V는 이제 F에서 P로 임의의 번호 r을₁ 보낸다.
• 단계 1: P는 $f{\displaystyle {}_{}}$ ${\displaystyle i_{}}$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle r_{}}$ ${\displaystyle {\mathrm{i}}_{}}$- ${\displaystyle 1{}_{}}$, z${\displaystyle }$) ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},z)$의 계수를 z의 다항식으로 전송한다$$.V verifies that the degree of f_i is less than n and that ${\displaystyle f_{i-1}(r_{1},\dots ,r_{i-1})=f_{i}(r_{1},\dots ,r_{i-1},0)+f_{i}(r_{1},\dots ,r_{i-1},1)}$. (If not V rejects).V는 이제 F에서 P로 임의의 번호 r을_i 보낸다.
• 단계 n+1: V는 ${\displaystyle p_{}}$${\displaystyle }$( ${\displaystyle {r\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle r_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle p(r_{1},\dots ,r_{n}}$을(를) $f{\displaystyle {}_{}}$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$, , r ${\displaystyle n_{}}$) ${\displaysty f_{n}(r_{1},\dots ,r_{n})$ 값과 비교하기 위해$$ 평가한다$.$ V가 동일하면 V가 거부한다.

이 알고리즘은 퍼블릭 코인 알고리즘이라는 점에 유의하십시오.

만약 φ에게 만족스러운 과제가 있다면, V는 분명히 받아들일 것이다.φ에 k-만족 과제가 없는 경우, φ에 k-만족 과제가 있음을 V에 납득시키려고 노력하는$$ $p{\displaystyle \stackrel{}{}}$~ ${\$이(가) 있다고 가정한다.우리는 이것이 오직 낮은 확률에서만 이루어질 수 있다는 것을 보여준다.

0단계에서 V이 거부되지 않도록 $하려면{\displaystyle \stackrel{}{}}$ P${\displaystyle \stackrel{}{}}$~ ${\$이(가) 잘못된 $값{\displaystyle {\stackrel{}{}}_{}}$f ~ ${\displaystyle 0_{\mathrm{}}}$) ${\displaystyle {\f}_{0}()$을(를) P로 전송해야$$ 한다.Then, in phase 1, ${\displaystyle {\tilde {P}}}$ must send an incorrect polynomial ${\displaystyle {\tilde {f}}_{1}}$ with the property that ${\displaystyle {\tilde {f}}_{1}(0)+{\tilde {f}}_{1}(1)={\tilde {f}}_{0}()}$. When V chooses a무작위 r을₁ P로 보낼 것,

${\displaystyle \Pr \left[{\tilde {f}_{1}(r_{1})=f_{1}(r_{1}\right]<{\tfrac {1}{n^{2}}.}$

이는 최대 d의 단일 변수에 있는 다항식은 d 루트를 초과할 수 없기 때문이다(항상 0으로 평가하지 않는 한).따라서 최대 d의 단일 변수에 있는 모든 두 다항식은 d 장소에서만 같을 수 있다.F > 2이므로ⁿ r이₁ 이 값들 중 하나가 될 확률은 최대 / < n/ ${\$}{n$}}<n/n^{n}}},$ 최대 (n/$1000$) ≤ (n/n³)이다.

이 아이디어를 각 1 ≤ i ≤ n에 대해 일반화한다.

${\displaystyle {\tilde{f}_{i-1}(r_{1},\re_{i-1})\neq f_{i-1}(r_{1},\re_{i-1}),}$

F에서 무작위로 선택한 r의_i 경우,

${\displaystyle \Pr \왼쪽[{\tilde{f}}(r_{1},\dots,r_{i}})=f_{i}(r_{1},\dots,r_{i}\ri}\right]\leq {\tfrac {1}{n^{2}}.}$

위상은 n개이므로, V가 어느 단계에서 편리한_i r을 선택하기 $때문$에${\displaystyle \stackrel{}{}}$P ~$${\$displaystyle {\tilde{$P}}가 운이 좋을$$ 확률은 최대 1/n이다.따라서 어떤 프로베라도 검증자가 1/n보다 큰 확률로 수용하게 할 수 없다.우리는 또한 검증자 V가 확률론적 다항식 시간에 작동한다는 것을 정의에서 알 수 있다.따라서 #SAT ∈ IP.

TQBF는 IP의 구성원이다.

PSPACE가 IP의 서브셋임을 보여주기 위해서는 PSPACE-완전한 문제를 선택하고 IP에 있음을 보여줄 필요가 있다.일단 이것을 보여주면, PSPACE ⊆ IP가 확실해진다.여기서 증명된 증명 기술은 Adi Shamir에게 인정된다.

우리는 TQBF가 PSpace-Complete에 있다는 것을 안다.따라서 ψ은 계량화된 부울식이어야 한다.

${\displaystyle \psi ={\mathsf {Q}_{1}x_{1}\dots {\mathsf {Q}x_{m}[\varphi ]}$

여기서 φ은 CNF 공식이다.그 다음 Q는_i ∃ 또는 ∀ 중 하나의 정량화다.now_i f는 이전의 증명과 동일하지만, 지금은 정량자도 포함한다.

${\displaystyle f_{i}(a_{1},\dots ,a_{i})={\begin{cases}f_{i}(a_{1},\dots ,a_{m})=1&{\mathsf {Q}}_{i+1}x_{i+1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi (a_{1},\dots ,a_{i})]{\text{ is true}}\\0&{\text{otherwise}}\end{cases}}}$

여기서 φ(a₁, ..., a_i)는 x 대₁ x로_i 대체하는_i a와₁ 함께 φ이다.따라서 f는₀ ψ의 진리값이다.arithmet을 산술화하려면 다음 규칙을 사용해야 한다.

${\displaystyle f_{i}(a_{1},\dots ,a_{i})={\begin{cases}f_{i+1}(a_{1},\dots ,a_{i},0)\cdot f_{i+1}(a_{1},\dots ,a_{i},1)&{\mathsf {Q}}_{i+1}=\forall \\f_{i+1}(a_{1},\dots ,a_{i},0)*f_{i+1}(a_{1},\dots ,a_{i},1)&{\mathsf {Q}}_{i+1}=\exists \end{cases}}}$

여기서 x ∗ y = 1 - (1 - x)(1 - y).

#SAT에 기술된 방법을 사용함으로써, 우리는_i 결과 다항식의 정도가 각 정량자와 함께 두 배가 될 수 있는 문제에 직면해야 한다.이를 방지하기 위해서는 부울 입력에 대한 거동 변화 없이 다항식의 정도를 낮추는 새로운 감속 연산자 R을 도입해야 한다.

따라서 이제 산술화 $\psi {\displaystyle }$= ${\displaystyle {\mathsf{}}_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$… ${\displaystyle {\mathsf{}}_{}}$ ${\displaystyle m_{}}$ ${\displaystyle x}$ ${\displaystyle m_{}}$[ ] ${\displaystyle ]}$ ${\displaystyle \psi ={{Q}_{1}x_{1}}\dots {\mathsf{Q}_{m}x_{m}[\varphi ]}}}}$을(를) 하기 전에 다음과$$ 같은 새로운 표현을 도입한다.

${\displaystyle \psi '={\mathsf {Q}}_{1}\mathrm {R} x_{1}{\mathsf {Q}}_{2}\mathrm {R} x_{1}\mathrm {R} x_{2}\dots {\mathsf {Q}}_{m}\mathrm {R} x_{1}\dots \mathrm {R} x_{m}[\varphi ]}$

또는 다른 방법으로:

${\displaystyle \psi '={\mathsf {S}}_{1}y_{1}\dots {\mathsf {S}}_{k}y_{k}[\varphi ],\qquad {\text{ where }}{\mathsf {S}}_{i}\in \{\forall ,\exists ,\mathrm {R} \},\ y_{i}\in \{x_{1},\dots ,x_{m}\}}$

이제 모든 i ≤ k에 대해 f_i 함수를 정의한다.$또한{\displaystyle {}_{}}$ f ${\displaystyle k_{}}$( ${\displaystyle {x\mathrm{}}_{}}$ 1${\displaystyle }$, …${\displaystyle }$, ${\displaystyle x_{}}$m )$${\$displaystyle f_{k}(x_{1},\dots ,x_{m})$를 산술화하여 얻은 다항식 p(x₁, ..., x_m)로$$ 정의한다.이제 다항식의 정도를 낮게 유지하기 위해 f_ii+1:

${\displaystyle {\text{}}{{}\mathsf{S}_{i+1}=\all,\quad f_{i}(a_{1},\dots,a_{i})=f_{i1}(a_{1},\dots,a_{i},0)\cdot f_{i1},\cdots,a_{i1},a_{i1},a_{i1}.$

${\displaystyle {\text{}}{{}\mathsf{S}_{i+1}=\exists,\quad f_{i}(a_{1},\dots,a_{i})=f_{i+1}(a_{1},\dots,a_{i},0)*f_{i+1}(a_{1},dots,a_{i},a_},a_{i},a_{i},a_{i})$

${\displaystyle {\text{If }}{\mathsf {S}}_{i+1}=\mathrm {R} ,\quad f_{i}(a_{1},\dots ,a_{i},a)=(1-a)f_{i+1}(a_{1},\dots ,a_{i},0)+af_{i+1}(a_{1},\dots ,a_{i},1)}$

이제 우리는 R이 다항식의 정도를 바꾸지 않는다는 것을 알 수 있다.또한_x R 연산이 부울 입력에 대한 함수 값을 변경하지 않는지 확인하는 것이 중요하다.ψ의 그래서 f0은 여전히 최고 진리 값,지만 처방전 가치}우리는 xR은인데 또한 어떤 Q후에 선형은 결과 나는 x 나는{\displaystyle{\mathsf{Q}}_{나는}x_{나는}을 생산하 1때문에 R)나는{\displaystyle \mathrm{R}_{x_{1}}\dots\mathrm{R}_{x_{나는}}}에 ψ′기 위해 줄이려는도 아래로 1후 arithmetizi.nG $Q{\displaystyle {\mathsf{}}_{}}$ ${\displaystyle i_{}}$ ${\$

이제 프로토콜을 설명해보자.n이 ψ의 길이인 경우, 프로토콜의 모든 산술 연산은 적어도 n의⁴ 크기 필드를 초과한다. 여기서 n은 ψ의 길이다.

• 0단계: P → V: P는 V로 f를₀ 보낸다.V는 f₀=1을 확인하고 그렇지 않으면 거부한다.
• 1단계: P → V: P는 V에 f₁(z)를 보낸다.V는 계수를 사용하여 f₁(0)와 f₁(1)를 평가한다.그런 다음 다항식 학위가 기껏해야 n이고 다음과 같은 정체성이 참인지 확인한다.

${\displaystyle f_{0}(\varnothing )={\begin{cases}f_{1}(0)\cdot f_{1}(1)&{\text{ if }}{\mathsf {S}}=\forall \\f_{1}(0)*f_{1}(1)&{\text{ if }}{\mathsf {S}}=\exists .\\(1-r)f_{1}(0)+rf_{1}(1)&{\text{ if }}{\mathsf {S}}=\mathrm {R} .\end{cases}}}$

어느 한쪽이 실패하면 거절한다.

• Phase i: P → V: P sends ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},z)}$ as a polynomial in z. r₁ denotes the previously set random values for ${\displaystyle r_{1},\dots ,r_{i-1}}$

V uses coefficients to evaluate ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},0)}$ and ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},1)}$. Then it checks that the polynomial degree is at most n and that the following identities are true:

${\displaystyle f_{i-1}(r_{1},\dots ,r_{i-1})={\begin{cases}f_{i}(r_{1},\dots ,r_{i-1},0)\cdot f_{i}(r_{1},\dots ,r_{i-1},1)&{\mathsf {S}}=\forall \\f_{i}(r_{1},\dots ,r_{i-1},0)*f_{i}(r_{1},\dots ,r_{i-1},1)&{\mathsf {S}}=\exists .\end{case}}}$

${\displaystyle f_{i-1}(r_{1}\dots r)=(1-r)f_{i}(r_{1},\dots ,r_{i-1},0)+rf_{i}(r_{1},\dots ,r_{i-1},1){\text{ if }}{\mathsf {S}}=\mathrm {R} .}$

어느 한쪽이 실패하면 거절한다.

V → P: V는 F에서 무작위 r을 선택하여 P로 보낸다($S{\displaystyle \mathsf{}}$= ${\displaystyle R\mathrm{}}$ ${\$ 그러면$$ 이 r은 이전 r을 대체한다.

P가 반드시 V를 설득하여 ${\displaystyle f_{}}$ $i{\displaystyle {}_{}}$ r ${\displaystyle 1{}_{}}$,${\displaystyle }$…${\displaystyle }$, r${\displaystyle }$) ${\displaystyle f_{i}(r_{1},\dots ,r)}$이(가) 올바른지 확인해야 하는 Goto 단계 i + 1이다.

• 단계 k + 1: ${\displaystyle {}_{}}$는 $p{\displaystyle }$( ${\displaystyle {r\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, r${\displaystyle {}_{}{m}_{}}$ ) ${\displaystyle p(r_{1},\dots ,r_{m}}$를 평가한다$.$그런 다음 $p{\displaystyle (}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… , ${\displaystyle r_{}}$m${\displaystyle }$) = ${\displaystyle f_{}}$k ( ${\displaystyle {r\mathrm{}}_{}}$1${\displaystyle }$, …${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle m_{}}$) ${\displaystyle$p($r_{1},\dots ,r_{m}=f_{k}(r_{1},\dots ,r_{m})$가 같으면 V가 수락하고, 그렇지 않으면 V가 거부한다.

이것이 프로토콜 설명의 끝이다.

만약 ψ이 사실이라면, V는 P가 프로토콜을 따를 때 받아들인다.마찬가지로 $P{\displaystyle \stackrel{}{}}$~ ${\$이(가) 거짓인 경우 P ~${\$은(는) 0단계에 놓여 f에₀ 대한 값을 전송해야 한다$$.If at phase i, V has an incorrect value for ${\displaystyle f_{i-1}(r_{1},\dots )}$ then ${\displaystyle f_{i}(r_{1},\dots ,0)}$ and ${\displaystyle f_{i}(r_{1},\dots ,1)}$ will likely also be incorrect, and so forth.$P{\displaystyle \stackrel{}{}}$~ ${\$이(가) 어떤$$ 랜덤 r에서 운이 좋을 확률은 다항식의 정도를 필드 크기로 나눈 값($n{\displaystyle }$/ ${\displaystyle n{}^{}}$ / ${\displaystyle {n\mathrm{}}^{}}$ 4 ${\$프로토콜은 O(n²) 단계를 통해 $실행$되므로${\displaystyle \stackrel{}{}}$P ~$${\$displaystyle${\$tilde{P}}$이(가) 특정 단계에서 운이 좋을 확률은 ≤ 1/n이다.$P{\displaystyle \stackrel{}{}}$~ ${\$이(가) 결코 운이$$ 좋지 않은 경우, V는 k+1 단계에서 거부한다.

이제 IP ⊆ PSPACE와 PSPACE ip IP를 모두 보여 주었으므로 IP = PSPACE를 원하는 대로 결론을 내릴 수 있다.더욱이, 우리는 어떤 IP 알고리즘도 PSPACE에서 IP로의 축소가 이러한 속성을 가지고 있기 때문에 공개 코인으로 받아들여질 수 있다는 것을 보여주었다.

변형

인터랙티브 증명 시스템의 정의를 약간 수정하는 IP의 많은 변형들이 있다.우리는 여기서 더 잘 알려진 것들 중 몇 가지를 요약한다.

살짝 담그다

IP의 서브셋은 IP와 유사하지만 결정론적 검증자(즉, 무작위성이 없는)를 가진 결정론적 인터랙티브 프루프 클래스다.이 수업은 NP와 같다.

완벽한 완성도

IP의 동등한 정의는 언어의 문자열에서 높은 확률로 상호작용이 성공하는 조건을 항상 성공해야 하는 요구조건으로 대체한다.

${\displaystyle w\in L\Rightarrow \Pr[V\왼쪽 화살표 P{\text{ }w]=1}$

대화형 증명 시스템을 가진 어떤 언어라도 완벽한 완성도를 가진 쌍방향 증명 시스템이 주어질 수 있기 때문에, 겉으로 보기에 더 강렬해 보이는 "완벽한 완전성"의 기준은 복잡도 등급 IP를 바꾸지 않는다.^[4]

MIP

1988년 골드웨서 외는 두 개의 독립적인 프로버가 있는 MIP라고 불리는 IP를 기반으로 훨씬 더 강력한 인터랙티브 증명 시스템을 만들었다.두 지지자는 일단 검증자가 그들에게 메시지를 보내기 시작하면 의사소통을 할 수 없다.범죄자와 그의 파트너가 별도의 방에서 심문받으면 거짓말을 하는지를 알기가 더 쉬우듯이, 검증자를 속이려는 악의적인 프로베러는 그것이 재확인할 수 있는 또 다른 프로베러가 있다면 상당히 더 쉽게 찾아낼 수 있다.사실 이것은 바바이, 포트나우, 룬드가 모든 문제의 클래스인 MIP = NEXPTIME, 즉 기하급수적인 시간에 비계수적인 기계로 해결할 수 있는 매우 큰 클래스라는 것을 보여줄 수 있을 정도로 큰 도움이 된다.더욱이 NP의 모든 언어는 추가적인 가정 없이 MIP 시스템에서 영지식 증거를 가지고 있다. 이는 단방향 함수의 존재를 가정하는 IP에만 알려져 있다.

IPP

IPP(무경계 IP)는 우리가 BPP 검증기를 PP 검증기로 대체하는 IP의 변종이다.보다 정확히 말하면, 우리는 다음과 같이 완전성과 건전성 조건을 수정한다.

• 완전성: 만약 끈이 언어에 있다면, 정직한 검증자는 적어도 1/2 확률의 정직한 프로베라로 이 사실을 확신할 것이다.
• 건전성: 만약 그 끈이 언어에 없다면, 어떤 프로베라도 정직한 검증자에게 그 끈이 언어에 있다는 것을 확신시킬 수 없다. 다만 1/2 미만의 확률을 제외하고는 말이다.

IPP 또한 PSPACE와 동일하지만, IPP 프로토콜은 oracle에 관해서 IPP=PSPACE와 상당히 다르게 동작한다: 모든 oracle에 관해서는 IPP=PSPACE, 거의 모든 oracle에 관해서는 IP ≠ PSPACE.^[5]

QIP

QIP는 BQP 검증기로 BPP 검증기를 대체하는 IP 버전이며, 여기서 BQP는 다항식 시간에 양자 컴퓨터가 해결할 수 있는 문제의 등급이다.그 메시지들은 큐빗으로 구성되어 있다.^[6]2009년, Jain, Ji, Upadhye, Watoil은 QIP 또한 PSPACE와 동일하다는 것을 증명하여,^[7] 이러한 변화는 프로토콜에 추가적인 힘을 주지 않음을 암시했다.이는 QIP = QIP[3]이기 때문에 QIP가 EXPTIME에 포함된 Kitaev와 Wattil의 이전 결과가 줄어들어 3회 이상이 절대 필요하지 않다.^[8]

compIP

IPP와 QIP는 검증자에게 더 많은 힘을 주는 반면, 콤프(comp)IP 시스템(경쟁 IP 인증 시스템)은 프로베라를 약화시키는 방식으로 완전성 상태를 약화시킨다.

• 완전성: 만약 어떤 끈이 L 언어에 있다면, 정직한 검증자는 적어도 2/3의 확률로 정직하게 프로베라로 이 사실을 확신할 것이다.더욱이 프로베러는 언어 L에 대한 신탁에 대한 접근 권한을 주어진 확률론적 다항식 시간에 그렇게 할 것이다.

본질적으로, 이것은 프로베라를 언어에 대한 신탁에 접근할 수 있는 BPP 기계로 만들지만, 건전성 케이스가 아닌 완전성 케이스에서만 가능하다.개념은 언어가 콤프(comp)IP, 그리고 나서 그것을 결정하는 것만큼 어떤 의미에서는 쉽다는 것을 대화적으로 증명한다.신탁으로 프로베러는 문제를 쉽게 해결할 수 있지만, 그 힘의 제한으로 인해 어떤 것이든 검증자를 설득하기가 훨씬 더 어려워진다.사실, 콤프IP는 심지어 NP를 포함하는 것으로 알려져 있지 않거나 믿기지 않는다.

반면에, 그러한 시스템은 어렵다고 여겨지는 몇몇 문제들을 해결할 수 있다.다소 역설적으로 이러한 시스템이 NP를 모두 해결할 수 있다고는 생각되지 않지만, 자기 축소성으로 인해 NP 완성 문제를 모두 쉽게 해결할 수 있다.이는 언어 L이 NP-하드(NP-hard)가 아닐 경우 프로베라의 힘이 실질적으로 제한된다는 사실에서 기인한다(더 이상 그것의 신탁으로 모든 NP 문제를 결정할 수 없기 때문이다).

또한, 그래프 비이형성 문제(IP의 고전적 문제)도 복합적이다.IP, 프로베러가 해야 하는 유일한 하드 작업은 이소모르프 테스트뿐이므로, 이 테스트는 오라클을 사용하여 해결할 수 있다.2차적 비재점도 및 그래프 이형성 또한 복합적이다.IP.^[9] 참고, QNR이 UP 교차 co-UP에 있기 때문에 2차 비반복성(QNR)은 그래프 이형성보다 쉬운 문제일 가능성이 있다.^[10]

메모들

참조

• Babai, 무작위성을 위한 L. 트레이딩 그룹 이론.제17회 ACM 계산 이론 심포지엄의 진행. ACM, 1985년 뉴욕, 페이지 421–429.
• 샤피 골드워서, 실비오 미칼리, 찰스 라코프.대화형 교정 시스템의 지식 복잡성.제17회 ACM 심포지엄 로드아일랜드의 계산 이론에 관한 진행. 1985, 페이지 291–304.확장 추상화
• 샤피 골드워서와 마이클 시퍼.쌍방향 증명 시스템에서 개인 동전 대 공용 동전.제18회 연차 ACM 심포지엄 연산 이론 진행ACM, 1986년 뉴욕 페이지 59–68.
• 라훌 자인, 정펑지, 사르바그야 우파디야, 존 와틸리.QIP = PSPACE. [1]
• Lund, C, Fortnow, L, Karloff, H, Nisan, N. 대수학적으로 상호작용하는 증명 시스템을 위한 방법.컴퓨터 과학의 기초에 관한 제31회 심포지엄의 진행에서.IEEE, 뉴욕, 1990 페이지 2-90.
• 아디 샤미르.IP = PSPACE. ACM 저널, 제39권, 제4호, 페이지 869–877.1992년 10월.
• 알렉산더 심.IP=PSPACE: Simplified Proof.J.ACM, v. 39(4), 페이지 878–880, 1992.
• 복잡성 동물원: IP, MIP, IPP, QIP, QIP(2), compIP, frIP