IP (복잡도)

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

1. 개요
2. 정의
3. 변형
참조

1. 개요

IP(Interactive Proof)는 검증자와 증명자 간의 상호 작용을 통해 계산 문제를 해결하는 복잡도 클래스이다. IP는 언어 L이 IP에 속한다는 것을 정의하며, 아서-멀린 프로토콜과 밀접한 관련이 있다. IP는 PSPACE에 포함되며, PSPACE ⊆ IP임을 증명하여 IP = PSPACE임을 보인다. IP의 변형으로 dIP, 완전 완전성, MIP, IPP, QIP, compIP 등이 있다.

더 읽어볼만한 페이지

확률적 복잡도 종류 - BQP
BQP는 양자 컴퓨터를 사용하여 정의되는 계산 복잡도 클래스이며, 유계 오차를 갖는 양자 회로군으로 정의되고, P와 BPP를 포함하며 PP, PSPACE에 포함된다.
확률적 복잡도 종류 - RP (복잡도)
RP 복잡도 클래스는 확률적 튜링 기계가 언어에 속하는 입력에 대해 1을 출력할 확률이 1/2 이상이고, 속하지 않는 입력에 대해서는 항상 0을 출력하는 문제들의 집합으로, BPP, ZPP, co-RP와 관련되며 P-NP 문제와 연관성을 갖는 다항식 항등식 검사 문제의 예시를 포함한다.

IP (복잡도)
개요
분야	계산 복잡도 이론
복잡도 종류	PSPACE
정의	상호작용 증명 시스템으로, 증명자(prover)가 전능하고 검증자(verifier)는 다항 시간을 사용하는 경우.
특징	PSPACE와 동일함.
역사
발견	1980년대 후반, Lund 등이 대화형 증명 시스템 연구 중 발견.
중요 결과	IP = PSPACE (Lund, Fortnow, Karloff, Nisan 증명).
수학적 정의
정의	언어 L이 IP에 속하는 것은 다음 조건을 만족하는 다항 시간 튜링 기계 V (검증자)가 존재한다는 의미이다.
완전성	만약 x가 L에 속하면, 검증자 V는 높은 확률로 증명자 P와 상호작용하여 x가 L에 속한다는 것을 확신할 수 있다.
건전성	만약 x가 L에 속하지 않으면, 어떤 증명자 P'도 검증자 V를 높은 확률로 속여 x가 L에 속한다고 믿게 할 수 없다.
주요 성질
PSPACE와의 동등성	IP = PSPACE. 즉, PSPACE에 속하는 모든 문제는 대화형 증명 시스템을 통해 증명 가능하다.
확률적 알고리즘	검증자는 확률적 알고리즘을 사용하여 증명의 타당성을 검증한다.
상호작용성	증명자와 검증자는 여러 차례 메시지를 교환하며 증명을 진행한다.
관련 연구
PCP 정리	NP에 속하는 모든 문제는 확률적으로 검증 가능한 형태로 변환될 수 있음을 보여준다.
영지식 증명	증명의 유효성을 입증하면서도 증명 외의 어떤 정보도 드러내지 않는 증명 방식.
참고 문헌

2. 정의

계산 복잡도 이론에서 '''IP'''(Interactive Polynomial time)는 대화형 증명 시스템을 사용하여 다항 시간 안에 검증될 수 있는 문제들의 복잡도 종류를 나타낸다. 이 시스템은 강력한 계산 능력을 가진 증명자(''P'', Prover)와 확률적 다항 시간 계산 능력을 가진 검증자(''V'', Verifier) 사이의 상호작용을 통해 특정 주장의 참/거짓을 판단한다. 상세한 정의와 관련 개념은 하위 섹션에서 다룬다.

2. 1. IP의 정의

언어 ''L''이 '''IP'''에 속한다는 것은 어떤 문자열 ''w''가 언어 ''L''에 속하는지 아닌지를 확률적으로 검증할 수 있는 대화형 증명 시스템이 존재한다는 의미이다. 구체적으로는, 모든 입력 문자열 ''w''에 대해 다음 조건을 만족하는 검증자(''V'', Verifier)와 증명자(''P'', Prover)가 존재해야 한다.

:

w \in L \Rightarrow \Pr[V \leftrightarrow P\text{가 }w\text{를 수락}] \ge \tfrac{2}{3}

:

w \not \in L \Rightarrow \Pr[V \leftrightarrow Q\text{가 }w\text{를 수락}] \le \tfrac{1}{3}

여기서 ''Q''는 어떤 (악의적일 수 있는) 증명자를 의미한다. 첫 번째 조건은 문자열 ''w''가 실제로 언어 ''L''에 속할 경우, 정직한 증명자 ''P''와 검증자 ''V''가 상호작용하여 ''V''가 ''w''를 '언어에 속한다'고 수락할 확률이 최소 2/3 이상이어야 함을 뜻한다. 두 번째 조건은 ''w''가 ''L''에 속하지 않을 경우, 어떤 증명자 ''Q''가 검증자 ''V''를 속이려고 시도하더라도 ''V''가 ''w''를 잘못 수락할 확률이 최대 1/3 이하이어야 함을 뜻한다. 이 확률값 2/3와 1/3은 오류 확률을 임의로 작게 줄일 수 있다면 다른 값으로 대체될 수 있다.

러슬로 바바이가 소개한 아서-멀린 프로토콜은 '''IP'''와 본질적으로 유사하지만, 검증자와 증명자 간의 상호 작용 라운드 수가 다항 시간이 아닌 상수로 제한된다는 점에서 차이가 있다.

골드와서 등은 검증자가 사용하는 난수를 증명자에게 공개하는 '공개 동전' 프로토콜과 공개하지 않는 '비공개 동전' 프로토콜의 능력이 다르지 않음을 보였다. 비공개 동전 프로토콜의 효과를 공개 동전 프로토콜로 모방하는 데 최대 두 번의 추가 라운드만 필요하며, 반대로 검증자는 언제든 자신의 비공개 동전 던지기 결과를 증명자에게 보낼 수 있으므로 두 유형의 프로토콜은 본질적으로 동일한 계산 능력을 가진다.

'''IP'''는 계산 복잡도 이론에서 중요한 복잡도 종류 중 하나로, PSPACE와 동일하다는 것이 증명되었다 ('''IP''' = '''PSPACE'''). 이는 대화형 증명 시스템을 통해 다항 공간으로 풀 수 있는 모든 문제를 검증할 수 있음을 의미하며, 이는 전통적인 '''PSPACE''' 증명이 지수적으로 길 수 있다는 점과 대비된다.

2. 2. 아서-멀린 프로토콜

아서-멀린 프로토콜(Arthur–Merlin protocol)은 러슬로 바바이(László Babai)가 소개한 대화형 증명 시스템의 한 종류이다. 이 프로토콜은 일반적인 대화형 증명 시스템(IP)과 본질적으로 유사하지만, 증명자와 검증자 사이의 상호작용 횟수(라운드 수)가 다항식이 아닌 상수로 제한된다는 중요한 차이점이 있다.

2. 3. IP ⊆ PSPACE 증명

IP ⊆ PSPACE임을 증명하기 위해, 다항식 공간 기계에 의한 대화형 증명 시스템을 시뮬레이션한다. 이제 다음과 같이 정의할 수 있다.

:

\Pr[V\text{ accepts }w\text{ starting at }M_j] = \max\nolimits_P \Pr \left [V \leftrightarrow P\text{ accepts }w\text{ starting at }M_j \right ]

그리고 모든 0 ≤ ''j'' ≤ ''p'' 및 모든 메시지 기록 ''M_j''에 대해, 귀납적으로 함수 ''N_{M_j}''를 정의한다.

:

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}

여기서:

:

\text{wt-avg}_{m_{j+1}} N_{M_{j+1}} := \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_{M_j+1}''의 평균이다.

''M''₀를 빈 메시지 시퀀스로 간주하고, 여기서 ''N_M₀''가 다항식 공간에서 계산될 수 있고 ''N_M₀'' = Pr[''V'' accepts ''w'']임을 보인다. 먼저, ''N_M₀''를 계산하기 위해 알고리즘은 모든 ''j'' 및 ''M_j''에 대해 ''N_{M_j}'' 값을 재귀적으로 계산할 수 있다. 재귀의 깊이가 ''p''이므로 다항식 공간만 필요하다. 두 번째 요구 사항은 ''N_M₀'' = Pr[''V'' accepts ''w'']여야 한다는 것이다. 즉, ''w''가 A에 속하는지 여부를 결정하는 데 필요한 값이다. 이를 다음과 같이 귀납적으로 증명한다.

모든 0 ≤ ''j'' ≤ ''p'' 및 모든 ''M_j''에 대해, ''N_{M_j}'' = Pr[''V'' accepts ''w'' starting at ''M_j'']임을 보여야 하며, ''j''에 대해 귀납적으로 이를 수행한다. 기본 경우는 ''j'' = ''p''인 경우이다. 그런 다음 귀납법을 사용하여 ''p''에서 0으로 내려간다.

''j'' = ''p''인 기본 경우는 비교적 간단하다. ''m_p''가 accept 또는 reject이므로, ''m_p''가 accept이면 ''N_{M_p}''는 1로 정의되고 Pr[''V'' accepts ''w'' starting at ''M_j''] = 1이며, 메시지 스트림은 수락을 나타내므로 주장이 참이다. ''m_p''가 reject인 경우, 논증은 매우 유사하다.

귀납적 가설의 경우, 일부 ''j''+1 ≤ ''p'' 및 모든 메시지 시퀀스 ''M_j+1''에 대해, ''N_{M_j+1}'' = Pr[''V'' accepts ''w'' starting at ''M_j+1'']라고 가정하고, 그런 다음 ''j'' 및 모든 메시지 시퀀스 ''M_j''에 대해 가설을 증명한다.

''j''가 짝수이면, ''m_j+1''은 ''V''에서 ''P''로 가는 메시지이다. ''N_{M_j}''의 정의에 의해,

:

N_{M_j} = \sum\nolimits_{m_{j+1}} \Pr\nolimits_r \left [V(w,r,M_j)=m_{j+1} \right ] N_{M_{j+1}}.

그런 다음, 귀납적 가설에 의해, 이것은 다음과 같다.

:

\sum\nolimits_{m_{j+1}} \Pr\nolimits_r \left [V(w,r,M_j)=m_{j+1} \right ] * \Pr \left [V\text{ accepts }w\text{ starting at }M_{j+1} \right ].

마지막으로, 정의에 의해, 이것은 Pr[''V'' accepts ''w'' starting at ''M_j'']와 같다.

''j''가 홀수이면, ''m_j+1''은 ''P''에서 ''V''로 가는 메시지이다. 정의에 의해,

:

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

그런 다음, 귀납적 가설에 의해, 이것은 다음과 같다.

:

\max\nolimits_{m_{j+1}} * \Pr[V\text{ accepts }w\text{ starting at }M_{j+1}].

이것은 Pr[''V'' accepts ''w'' starting at ''M_j'']와 같다. 왜냐하면 다음과 같기 때문이다.

:

\max\nolimits_{m_{j+1}} \Pr[V\text{ accepts }w\text{ starting at }M_{j+1}] \leq \Pr[V\text{ accepts w starting at }M_j]

오른쪽의 증명자가 왼쪽의 표현식을 최대화하기 위해 메시지 ''m_j+1''을 보낼 수 있기 때문이다. 그리고:

:

\max\nolimits_{m_{j+1}} \Pr\left[V\text{ accepts }w\text{ starting at }M_{j+1} \right] \geq \Pr\left[V\text{ accepts }w\text{ starting at }M_j\right]

동일한 증명자는 동일한 메시지를 보내는 것보다 더 잘할 수 없기 때문이다. 따라서, 이것은 ''j''가 짝수이든 홀수이든 상관없이 유지되며, IP ⊆ PSPACE에 대한 증명이 완료된다.

여기서 특정 문자열 ''w''에 대해 최적의 증명자 ''P''를 사용하는 다항식 공간 기계를 구성했다. 우리는 모든 임의 입력 비트 집합을 다항식 공간에서 시도할 수 있기 때문에 임의 입력 비트를 사용하는 증명자 대신 이 최적의 증명자를 사용한다. 다항식 공간 기계로 대화형 증명 시스템을 시뮬레이션했으므로, 원하는 대로 IP ⊆ PSPACE임을 보여주었다.

2. 4. PSPACE ⊆ IP 증명

'''PSPACE''' ⊆ '''IP'''를 증명하는 데 사용될 기법을 설명하기 위해, 먼저 룬드 외 여러 사람이 증명한 더 약한 정리인 #SAT ∈ '''IP'''를 증명할 것이다. 그런 다음 이 증명의 개념을 사용하여 TQBF ∈ '''IP'''임을 보여주기 위해 확장할 것이다. TQBF는 PSPACE-완전 문제이고, TQBF ∈ '''IP'''이므로 '''PSPACE''' ⊆ '''IP'''라는 결론을 얻을 수 있다.

2. 4. 1. #SAT ∈ IP

먼저 #SAT 문제가 '''IP'''에 속함을 보이는 것으로 시작한다. 여기서 #SAT는 다음과 같이 정의된다.

:

\#\text{SAT} = \left \{ \langle \varphi, k \rangle \ : \ \varphi \text{는 정확히 } k \text{개의 만족하는 할당을 가진 CNF-formula이다} \right \}.

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

증명은 먼저 산술화(arithmetization)를 사용하여 ''n''개의 변수를 가진 부울 공식 φ(''b''₁, ..., ''b''_n'')을 다항식 ''p''_φ(''x''₁, ..., ''x''_n'')에 대응시키는 과정으로 이루어진다. 이 다항식 ''p''_φ는 φ가 참이면 1, 그렇지 않으면 0의 값을 가지며, 변수에는 부울 값(0 또는 1)이 할당된다. φ에서 사용된 부울 연산 ∨, ∧, ¬는 아래 표와 같이 ''p''_φ에서 특정 연산으로 대체되어 시뮬레이션된다.

부울 공식 φ(''b''₁, ..., ''b''_n'')을 다항식 ''p''_φ(''x''₁, ..., ''x''_n'')으로 변환하기 위한 산술화 규칙
부울 연산	다항식 연산
a ∧ b	ab
a ∨ b	a ∗ b := 1 − (1 − a)(1 − b)
¬a	1 − a

예를 들어, $\phi = a \and (b \or \neg c)$ 는 다음과 같이 다항식으로 변환된다.

: $\begin{align}p_\varphi &= a \wedge (b \vee \neg c) \\&= a \wedge \left (b * (1-c) \right ) \\&= a \wedge \left ( 1 - (1-b)(1 - (1-c)) \right ) \\&= a \left ( 1 - (1-b)(1 - (1-c)) \right ) \\&= a - (ac-abc)\end{align}$

연산 ''ab''와 ''a'' ∗ ''b''는 결과 다항식의 차수를 각 항의 차수의 합으로 제한하므로, 어떤 변수의 차수도 φ의 길이보다 커지지 않는다.

이제 ''F''를 차수 ''q'' > 2^''n''인 유한 필드로 설정한다. 또한 ''q''는 최소 1000 이상이어야 한다. 각 0 ≤ ''i'' ≤ ''n''에 대해, $a_1, \dots, a_{i-1}\in F$ 를 매개변수로 하고 단일 변수 $a_i \in F$ 를 갖는 ''F'' 상의 함수 ''f_i''를 다음과 같이 정의한다. 0 ≤ ''i'' ≤ ''n''이고 $a_1, \dots, a_i \in F$ 에 대해,

: $f_i(a_1, \dots, a_i) = \sum\nolimits_{a_{i+1}, \dots, a_n \in \{0, 1\}} p(a_1, \dots, a_n).$

여기서 ''f''₀의 값은 φ의 만족하는 할당의 수이다. ''f''₀는 변수가 없는 상수 함수이다.

#SAT에 대한 프로토콜은 다음과 같이 진행된다.

'''단계 0''': 증명자 ''P''는 소수 ''q'' > 2^''n''를 선택하고 ''f''₀을 계산한 다음, ''q''와 ''f''₀을 검증자 ''V''에게 보낸다. ''V''는 ''q''가 max(1000, 2^''n'')보다 큰 소수이고 ''f''₀() = ''k''인지 확인한다.
'''단계 1''': ''P''는 ''f''₁(''z'')를 ''z''에 대한 다항식으로 간주하고 그 계수들을 보낸다. ''V''는 ''f''₁의 차수가 ''n''보다 작고 ''f''₀ = ''f''₁(0) + ''f''₁(1)인지 확인한다. (만약 조건이 만족되지 않으면 ''V''는 거부한다). ''V''는 이제 ''F''에서 임의의 수 ''r''₁을 선택하여 ''P''에게 보낸다.
'''단계 i''' (2 ≤ ''i'' ≤ ''n''): ''P''는 $f_i(r_1, \dots, r_{i-1}, z)$ 를 ''z''에 대한 다항식으로 간주하고 그 계수들을 보낸다. ''V''는 ''f_i''의 차수가 ''n''보다 작고 $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)$ 인지 확인한다. (만약 조건이 만족되지 않으면 ''V''는 거부한다). ''V''는 이제 ''F''에서 임의의 수 ''r_i''를 선택하여 ''P''에게 보낸다.
'''단계 n+1''': ''V''는 $p(r_1, \dots, r_n)$ 을 직접 계산하여 ''P''가 마지막 단계에서 주장한 값 $f_n(r_1, \dots, r_n)$ 과 비교한다. 두 값이 같으면 ''V''는 수락하고, 다르면 거부한다.

이 프로토콜은 검증자가 무작위 수를 선택하여 증명자에게 보내는 공공 동전(public coin) 알고리즘이다.

만약 φ가 실제로 ''k''개의 만족하는 할당을 가진다면, 정직한 증명자 ''P''는 항상 검증자 ''V''가 수락하도록 만들 수 있다. 반대로, φ가 ''k''개의 만족하는 할당을 가지지 않는 경우, 부정직한 증명자

\tilde P

가 ''V''를 속이려 한다고 가정해보자.

단계 0에서 ''V''가 거부하지 않도록

\tilde P

는 잘못된 값

\tilde f_0() \neq k

를 보내야 한다. 단계 1에서

\tilde P

는

\tilde f_1(0)+\tilde f_1(1) = \tilde f_0()

를 만족하는 어떤 다항식

\tilde f_1

을 보내야 한다. 만약

\tilde f_1 \neq f_1

이라면 (즉,

\tilde P

가 거짓말을 한다면), ''V''가 무작위로 선택한 ''r''₁에 대해

\tilde f_1(r_1) = f_1(r_1)

일 확률은 슈워츠-지펠 보조정리에 의해 매우 낮다. 구체적으로, 차수가 최대 ''d''인 두 개의 서로 다른 단일 변수 다항식은 최대 ''d''개의 점에서만 같은 값을 가질 수 있다. 여기서 다항식의 차수는 ''n'' 이하이고 필드 ''F''의 크기 |''F''|는 2^''n''보다 크므로, 일치할 확률은 ''n''/|''F''| ≤ ''n''/2^''n'' 보다 작다. ''n''이 충분히 크면 이 확률은 매우 작아진다 (예:

n/2^n < 1/n^2

).

이 논리를 각 단계 ''i'' (1 ≤ ''i'' ≤ ''n'')에 대해 일반화할 수 있다. 만약 이전 단계에서

\tilde f_{i-1}(r_1, \dots, r_{i-1}) \neq f_{i-1}(r_1, \dots, r_{i-1})

이었다면, ''V''가 무작위로 선택한 ''r_i''에 대해

\tilde f_i(r_1, \dots, r_i) = f_i(r_1, \dots, r_i)

일 확률은 여전히

1/n^2

이하이다.

총 ''n''번의 상호작용 단계가 있으므로, 부정직한 증명자

\tilde P

가 모든 단계에서 운 좋게 ''V''를 속일 확률(즉, ''V''가 잘못된 주장을 수락할 확률)은 각 단계에서의 실패 확률을 합한 것보다 작거나 같다. 대략적으로 이 확률은 ''n'' × (''n''/|''F''|) ≤ ''n''²/2^''n'' 정도로 매우 작다. 따라서 어떤 증명자도 검증자가 1/''n''보다 큰 확률로 (잘못된 주장을) 수락하도록 만들 수 없다.

검증자 ''V''는 각 단계에서 다항식 계산과 확인을 수행하며, 이는 확률적 다항 시간 내에 완료될 수 있다. 따라서 #SAT는 '''IP'''에 속한다.

2. 4. 2. TQBF ∈ IP

PSPACE가 IP의 부분 집합임을 보이기 위해서는, PSPACE-완전 문제를 하나 선택하여 그것이 IP에 속함을 증명하면 충분하다. TQBF(Quantified Boolean Formula)는 PSPACE-완전 문제로 알려져 있으므로, TQBF가 IP에 속함을 보이면 PSPACE ⊆ IP가 증명된다. 이 증명 기법은 아디 샤미르가 제시했다.

ψ를 다음과 같은 정량화된 부울식(TQBF)이라고 하자.

:

\psi = \mathsf Q_1 x_1 \dots \mathsf Q_mx_m[\varphi]

여기서 φ는 CNF 형식이고, ''Q_i''는 전칭 양자(∀) 또는 존재 양자(∃)이다. 이제 각 단계 ''i''에 대한 함수 ''f_i''를 다음과 같이 정의한다. 이는 변수 ''x''₁부터 ''x''_i까지의 값이 각각 ''a''₁부터 ''a''_i로 주어졌을 때, 나머지 부분식의 진리값을 나타낸다.

:

f_i(a_1, \dots, a_i) =  \begin{cases}1 & \text{if } \mathsf Q_{i+1}x_{i+1}\dots \mathsf Q_mx_m[\varphi(a_1, \dots, a_i)] \text{ is true}\\0 & \text{otherwise}\end{cases}

여기서 φ(''a''₁, ..., ''a_i'')는 φ의 변수 ''x''₁부터 ''x''_i까지를 값 ''a''₁부터 ''a''_i''로 치환한 식이다. 따라서 ''f''₀는 ψ 전체의 진리값이다. 이 식을 산술화하기 위해 다음 규칙을 사용한다.

:

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) & \text{if } \mathsf Q_{i+1} = \forall \\f_{i+1}(a_1, \dots,a_i,0) * f_{i+1}(a_1, \dots,a_i,1) & \text{if } \mathsf Q_{i+1} = \exists\end{cases}

여기서 연산 ∗는 ''x'' ∗ ''y'' = 1 − (1 − ''x'')(1 − ''y'')로 정의되며, 이는 논리합(OR) 연산의 산술화된 형태이다.

#SAT 문제의 증명 방식과 유사하게 산술화를 진행하면, 각 양자(quantifier)를 처리할 때마다 결과 다항식의 차수가 두 배로 증가할 수 있다는 문제가 발생한다. 이를 해결하기 위해, 부울 입력(0 또는 1)에 대한 함수의 값은 변경하지 않으면서 다항식의 차수를 낮추는 새로운 감소 연산자 ''R''을 도입한다.

수정된 식 ψ'는 다음과 같다.

:

\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]

이를 다르게 표현하면 다음과 같다.

:

\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''를 정의한다. ''f_k''(''x''₁, ..., ''x''_m'')는 φ를 산술화하여 얻은 다항식 ''p''(''x''₁, ..., ''x''_m'')이다. 다항식의 차수를 낮게 유지하기 위해 ''f_i''를 ''f_i+1''을 이용하여 다음과 같이 정의한다.

:

\text{If }\mathsf S_{i+1} = \forall, \quad f_i(a_1,\dots,a_i) = f_{i+1}(a_1,\dots,a_i,0) \cdot f_{i+1}(a_1,\dots,a_i,1)

:

\text{If }\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,1)

:

\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) + a f_{i+1}(a_1,\dots,a_i,1)

감소 연산 R은 다항식의 차수를 증가시키지 않는다. 또한 R_''x'' 연산은 부울 입력에 대한 함수의 값을 바꾸지 않으므로, ''f''₀는 여전히 ψ의 진리값을 나타낸다. R_''x'' 연산은 ''x''에 대해 선형인 결과를 만든다. ψ'에서 각

\mathsf Q_i x_i

뒤에

\mathrm R_{x_1}\dots \mathrm R_{x_i}

를 추가함으로써,

\mathsf Q_i

를 산술화한 후 높아진 차수를 다시 1로 낮출 수 있다.

이제 TQBF가 IP에 속함을 보이는 상호작용 증명 프로토콜을 설명한다. ''n''을 ψ의 길이라고 할 때, 프로토콜의 모든 산술 연산은 ''n''⁴ 이상 크기의 필드 ''F'' 위에서 수행된다. 증명자(Prover, P)는 ψ가 참임을 검증자(Verifier, V)에게 납득시키려 한다.

단계 0:
''P'' → ''V'': ''P''는 ''f''₀의 값(ψ의 진리값)을 ''V''에게 보낸다.
''V'': ''f''₀ = 1인지 확인한다. 만약 1이 아니면 거부(reject)한다.

단계 1:
''P'' → ''V'': ''P''는 ''f''₁(''z'')를 ''z''에 대한 다항식 형태로 ''V''에게 보낸다.
''V'':

1. 받은 다항식의 차수가 최대 ''n''인지 확인한다.

2. 다항식의 계수를 사용하여 ''f''₁(0)과 ''f''₁(1)을 계산한다.

3. 다음 항등식이 성립하는지 확인한다.

:

f_{0}(\varnothing) = \begin{cases}            f_{1}(0)\cdot f_{1}(1) & \text{ if }\mathsf S_1 = \forall \\            f_{1}(0) * f_{1}(1) & \text{ if }\mathsf S_1 = \exists \\            (1-r_1)f_{1}(0) + r_1 f_{1}(1) & \text{ if }\mathsf S_1 = \mathrm R \quad (\text{여기서 } r_1 \text{은 V가 선택할 임의의 값})            \end{cases}

(만약 S₁ = R 이면, V는 필드 F에서 임의의 값 r₁을 선택하여 P에게 보낸다. 그렇지 않으면 이 단계에서 값을 보내지 않는다.)

4. 위 조건 중 하나라도 만족하지 않으면 거부한다.

단계 i (''i'' > 1):
''P'' → ''V'': ''P''는 $f_i(r_1,\dots,r_{j},z)$ 를 ''z''에 대한 다항식 형태로 ''V''에게 보낸다. 여기서 $r_1,\dots,r_{j}$ 는 이전 단계들에서 V가 R 연산자를 만났을 때 선택한 임의의 값들이다. (변수 ''y_i''에 대응하는 임의의 값)
''V'':

1. 받은 다항식의 차수가 최대 ''n''인지 확인한다.

2. 다항식의 계수를 사용하여

f_i(r_1,\dots,r_{j},0)

과

f_i(r_1,\dots,r_{j},1)

을 계산한다.

3. 다음 항등식이 성립하는지 확인한다. (이전 단계에서 계산된

f_{i-1}(r_1,\dots,r_{j})

값 사용)

:

f_{i-1}(r_1,\dots,r_{j}) = \begin{cases} f_{i}(r_1,\dots,r_{j},0)\cdot f_{i}(r_1,\dots, r_{j},1) & \text{if } \mathsf S_i = \forall \\            f_{i}(r_1,\dots,r_{j},0) * f_i(r_1, \dots,r_{j},1) & \text{if } \mathsf S_i = \exists \\            (1-r_{j+1})f_{i}(r_1,\dots,r_{j},0) + r_{j+1}f_{i}(r_1,\dots,r_{j},1) & \text{if } \mathsf S_i = \mathrm R \quad (\text{여기서 } r_{j+1} \text{은 V가 선택할 새로운 임의의 값})            \end{cases}

4. 위 조건 중 하나라도 만족하지 않으면 거부한다.

''V'' → ''P'' (만약 $\mathsf S_i = \mathrm R$ 인 경우): ''V''는 필드 ''F''에서 임의의 값 ''r_j+1''을 선택하여 ''P''에게 보낸다.

단계 ''k'' + 1:
''V'': 모든 R 연산자에 대해 선택된 임의의 값들 $r_1,\dots,r_m$ (원래 변수 ''x''₁부터 ''x''_m에 대응)을 사용하여 최종 다항식 ''p''(''r''₁, ..., ''r''_m'')의 값을 직접 계산한다.
''V'': 이전 단계(단계 k)에서 얻은 $f_k(r_1,\dots,r_m)$ 값과 직접 계산한 $p(r_1,\dots,r_m)$ 값이 같은지 확인한다.
''V'': 두 값이 같으면 수락(accept)하고, 다르면 거부한다.

완전성(Completeness): 만약 ψ가 참(true)이면, 정직한 증명자 ''P''는 항상 검증자 ''V''가 수락하도록 프로토콜을 따를 수 있다. 각 단계에서 ''P''가 보내는 다항식은 올바르게 계산된 ''f_i''이므로, ''V''의 모든 검증은 통과될 것이다.
건전성(Soundness): 만약 ψ가 거짓(false)이면, 악의적인 증명자

\tilde{P}

가 검증자 ''V''를 속여 수락하게 만들 확률은 매우 낮다. ψ가 거짓이면 ''f''₀ = 0 이지만,

\tilde{P}

는 단계 0에서 ''f''₀ = 1이라고 주장해야 한다. 이후 단계 ''i''에서 ''V''가 이전 단계 값

f_{i-1}(r_1,\dots)

에 대해 잘못된 값을 가지고 있다면,

\tilde{P}

가 제시하는

f_i(\dots, z)

다항식은 ''V''의 검증 조건을 만족시키기 어렵다. 슈워츠-지펠 보조정리(Schwartz–Zippel lemma)에 따라, 잘못된 다항식이 특정 임의의 값 ''r''에 대해 우연히 올바른 값을 가질 확률은 다항식의 차수(''n'')를 필드의 크기(''n''⁴ 이상)로 나눈 값, 즉 ''n''/''n''⁴ = 1/''n''³ 이하이다. 프로토콜은 총 ''k'' = O(''n''²) 단계로 이루어지므로,

\tilde{P}

가 모든 단계를 성공적으로 속일 확률은 매우 작다 (대략 ''k''/''n''³ 수준). 따라서 ''V''는 높은 확률로 단계 ''k''+1에서

\tilde{P}

의 주장이 거짓임을 발견하고 거부할 것이다.

이 프로토콜은 TQBF 문제가 IP에 속함을 보여준다. TQBF는 PSPACE-완전 문제이므로, 이는 PSPACE ⊆ IP 임을 증명한다.

3. 변형

IP의 대화형 증명 시스템 정의를 약간 수정하는 여러 변형이 있다. 여기서는 잘 알려진 몇 가지를 요약한다.

3. 1. dIP

`'''IP'''`의 부분 집합으로 '''결정론적 대화형 증명''' 클래스가 있다. 이는 `'''IP'''`와 유사하지만, 검증자가 결정론적이라는 점, 즉 무작위성이 없다는 점이 다르다. 이 클래스는 '''NP'''와 동일하다.

3. 2. 완전 완전성 (Perfect Completeness)

IP의 정의를 다르게 내릴 수도 있다. 원래 정의는 상호작용이 언어 내의 문자열에 대해 높은 확률로 성공해야 한다는 것이지만, 이를 상호작용이 항상 성공해야 한다는 조건으로 바꿀 수 있다.

수식으로는 다음과 같이 표현된다.

:

w \in L \Rightarrow \Pr[V \leftrightarrow P\text{ accepts }w] = 1

이렇게 증명자가 항상 검증자를 설득할 수 있는 경우를 완전 완전성(Perfect Completeness)이라고 부른다. 이 조건은 원래 정의보다 더 강력해 보이지만, 실제로는 IP라는 복잡도 클래스 자체를 바꾸지는 않는다. 왜냐하면 상호작용 증명 시스템을 가진 모든 언어는 완전 완전성을 만족하는 상호작용 증명 시스템으로 변환될 수 있기 때문이다.^[4]

3. 3. MIP

1988년 골드와서 등은 '''IP'''를 기반으로 더 강력한 대화형 증명 시스템인 '''MIP'''(다중 증명자 대화형 증명)를 만들었다. 이 시스템에는 두 명 이상의 독립적인 증명자가 존재하며, 이 증명자들은 검증자가 메시지 전송을 시작하면 더 이상 서로 통신할 수 없다. 이는 마치 범죄 용의자를 공범과 분리하여 심문할 때 거짓말을 간파하기 쉬운 것과 유사하다. 즉, 악의적인 증명자가 검증자를 속이려 할 때 다른 증명자를 통해 교차 확인하면 탐지하기가 훨씬 쉬워진다.

이러한 특징의 유용성 덕분에 바바이, 포트노, 룬드는 '''MIP'''가 '''NEXPTIME'''과 동일함을 증명할 수 있었다. '''NEXPTIME'''은 지수 시간 내에 비결정적 튜링 기계로 풀 수 있는 모든 문제의 복잡도 종류로, 매우 큰 범위의 문제들을 포함한다. 또한, '''NP'''에 속하는 모든 언어는 어떠한 추가적인 가정 없이도 '''MIP''' 시스템에서 영지식 증명을 가질 수 있다. 이는 '''IP'''의 경우 일방향 함수의 존재를 가정해야만 가능한 것과 대비된다.

3. 4. IPP

'''IPP''' (''무제한 IP'')는 '''IP'''에서 검증자를 '''BPP''' 대신 '''PP'''(확률적 다항 시간) 기계로 사용하는 변형이다. 구체적으로, 완전성과 건전성 조건은 다음과 같이 수정된다.

'''완전성''': 어떤 문자열이 특정 언어에 속할 경우, 정직한 검증자는 정직한 증명자의 도움을 받아 최소 1/2의 확률로 이 사실을 확신할 수 있다.
'''건전성''': 어떤 문자열이 언어에 속하지 않을 경우, 어떤 증명자도 정직한 검증자에게 해당 문자열이 언어에 속한다고 1/2 미만의 확률을 초과하여 확신시킬 수 없다.

'''IPP'''는 '''PSPACE'''와 동일한 계산 능력을 가지는 것으로 알려져 있다. 그러나 '''IPP''' 프로토콜은 오라클 머신과 관련하여 '''IP'''와는 상당히 다르게 작동한다. 모든 오라클에 대해 '''IPP'''는 '''PSPACE'''와 같지만, '''IP'''는 거의 모든 오라클에 대해 '''PSPACE'''와 같지 않다.^[5]

3. 5. QIP

'''QIP'''(Quantum Interactive Proof)는 기존의 '''IP'''에서 확률적 다항 시간(BPP) 검증자를 양자 다항 시간(BQP) 검증자로 바꾼 형태이다.^[6] '''BQP'''는 양자 컴퓨터를 사용하여 다항 시간 안에 풀 수 있는 문제들의 복잡도 종류를 의미한다. QIP에서는 증명자와 검증자가 큐비트로 구성된 메시지를 주고받는다.

2009년, 자인(Jain), 지(Ji), 업아디야이(Upadhyay), 와트러스(Watrous)는 '''QIP'''가 '''PSPACE'''와 동일하다는 것을 증명했다.^[7] 이는 검증자를 양자 컴퓨터로 바꾸더라도 프로토콜의 계산 능력이 더 강해지지 않음을 보여준다. 또한, 이 연구는 '''QIP'''가 3개의 메시지만으로 충분하며(즉, '''QIP''' = '''QIP'''[3]), 더 많은 메시지 교환이 필요 없다는 사실도 밝혔다. 이는 이전에 키타예프(Kitaev)와 와트러스가 증명했던 '''QIP'''가 '''EXPTIME'''에 포함된다는 결과를 자연스럽게 포함한다.^[8]

3. 6. compIP

'''compIP''' (경쟁적 IP 증명 시스템, Competitive IP proof systems^eng)는 IPP나 QIP처럼 검증자에게 더 많은 권한을 부여하는 대신, 증명자의 능력을 제한하는 방식으로 작동하는 대화형 증명 시스템이다. 이는 시스템의 완전성 조건을 완화함으로써 이루어진다.

'''완전성''': 어떤 문자열이 특정 언어 ''L''에 속할 경우, 정직한 검증자는 정직한 증명자를 통해 최소 2/3의 확률로 그 사실을 확신할 수 있다. 이때, 증명자는 언어 ''L''에 대한 오라클에 접근할 수 있으며, 확률적 다항 시간 내에 증명을 수행한다.

본질적으로 이 조건은 완전성 경우에 한해, 증명자를 언어 ''L''에 대한 오라클 접근 권한을 가진 BPP 기계로 간주하게 한다. 하지만 건전성의 경우에는 해당되지 않는다. '''compIP'''의 핵심 개념은 어떤 언어가 '''compIP'''에 속한다면, 상호작용을 통해 해당 언어의 문제를 증명하는 것이 어떤 측면에서는 문제를 결정하는 것만큼 쉽다는 점이다. 오라클 덕분에 증명자는 문제를 쉽게 풀 수 있지만, 제한된 능력으로 인해 검증자를 설득하는 것은 훨씬 더 어려워진다. 이러한 특징 때문에 '''compIP'''는 NP를 포함하지 않는다고 여겨진다.^[9]

하지만 '''compIP'''는 NP 전체를 포함하지는 못할 것으로 보임에도 불구하고, 어려운 문제로 간주되는 일부 문제들을 해결할 수 있다. 예를 들어, 자기 축소성(self-reducibility)이라는 성질 덕분에 모든 NP-완전 문제를 쉽게 풀 수 있다. 다만 이는 해당 언어 L이 NP-hard가 아닌 경우, 증명자의 권한이 실질적으로 제한되기 때문에(더 이상 오라클을 사용하여 모든 NP 문제를 결정할 수 없으므로) 한계가 있다.^[9]

또한, IP의 고전적인 문제인 그래프 동형 문제도 '''compIP'''에 속한다. 이는 증명자가 수행해야 할 가장 어려운 연산이 그래프 동형성 검사인데, 이를 오라클을 통해 해결할 수 있기 때문이다. 이차 비잉여성 문제(Quadratic non-residue problem) 역시 '''compIP'''에 포함된다.^[9] 참고로, 이차 비잉여성 문제는 UP와 co-UP의 교집합에 속하므로, 그래프 동형 문제보다 더 쉬운 문제일 가능성이 높다.^[10]

참조

_[1] 서적 Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science IEEE Comput. Soc. Press
_[2] 논문 Ip= pspace.
_[3] 간행물 The random oracle hypothesis is false
_[4] 간행물 On Completeness and Soundness in Interactive Proof Systems
_[5] 뉴스 The random oracle hypothesis is false http://citeseer.ist.[...]
_[6] 뉴스 PSPACE has constant-round quantum interactive proof systems http://citeseer.ist.[...]
_[7] arXiv QIP = PSPACE
_[8] 뉴스 Parallelization, amplification, and exponential time simulation of quantum interactive proof systems https://cs.uwaterloo[...]
_[9] 뉴스 The Complexity of Decision versus Search http://www.cs.ucsd.e[...]
_[10] 간행물 A note on quadratic residuosity and '''UP'''

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com