NP의 다른 정의 — 검증자와 증명서

NP를 “NTM이 다항식 시간에 푸는 문제”라 정의했다. 그런데 NP에는 전혀 다른, 더 직관적인 정의가 존재한다. 두 정의는 완전히 동치다.

앞선 글에서 NP를 “NTM이 다항식 시간에 결정하는 언어 클래스”로 정의했다. 이 정의는 수학적으로 명확하지만, 현실에서 NTM은 존재하지 않는다. NP를 더 현실적으로 이해할 수 있는 동치 정의가 있다.

---

NP의 두 가지 정의

Df1: NTM 기반 정의

$$L \in NP \iff \exists \text{ 다항식 시간 NTM } M : L = L(M)$$

NTM이 모든 계산 경로를 동시에 탐색하는 것을 허용한다. 경로 중 하나라도 accept 상태에 도달하면 accept한다.

Df2: 검증자(Verifier) 기반 정의

$$L \in NP \iff \exists \text{ 다항식 시간 DTM (검증자) } V,\ \exists \text{ 다항식 } p :$$ $$x \in L \iff \exists h,\ |h| \leq p(|x|) : V(x, h) = \text{Yes}$$

여기서 $h$를 증명서(Certificate) 또는 증인(Witness) 이라 한다. $x$가 언어에 속한다는 사실을 증명해주는 힌트다.

---

증명서란 무엇인가?

증명서 $h$는 네 가지 조건을 만족해야 한다.

1. 존재 조건: $x \in L$이면, $V(x, h) = \text{Yes}$인 $h$가 반드시 존재한다.
2. 건전성 조건: $x \notin L$이면, 어떤 $h$를 제시해도 $V(x, h) = \text{No}$다.
3. 길이 조건: $|h| \leq p(|x|)$ — 입력 크기에 대한 다항식 이하
4. 효율성 조건: $V(x, h)$가 다항식 시간에 Yes/No를 판정

조건 1과 2의 비대칭성 이 핵심이다. 증명서 $h$는 “$x$가 L에 속함”을 증명할 수 있지만, $h$가 없다는 사실이 “$x$가 L에 속하지 않음”을 증명하지는 않는다. 즉, V가 No를 출력했다고 해서 $x \notin L$이라는 뜻이 아니다 — 단지 그 $h$가 올바른 증명서가 아닌 것이다.

구체적인 예: Longest Path 문제

그래프 $G$, 두 정점 $s, t$, 정수 $k$가 주어졌을 때, $G$에서 $s$에서 $t$까지의 단순 경로 중 길이가 $k$ 이상인 것이 존재하는지 판별하는 문제다.

• 증명서: 길이 $k$ 이상의 구체적인 경로 (정점 목록)
• 검증: 주어진 경로가 단순 경로인지, 길이가 $k$ 이상인지 확인 — 다항식 시간

증명서 없이 이 경로를 찾는 것(결정)은 어렵지만, 누군가 경로를 알려주면 검증은 쉽다. 이것이 NP의 핵심 직관이다.

---

암호학적 함의: 힌트의 비대칭성

“답을 찾기는 어렵고 맞는지 확인하기는 쉽다”는 비대칭성은 암호가 서 있는 자리와 모양이 같다.

• Bob(수신자): 암호문 $c$와 비밀키 $k$를 가진다. 복호화 알고리즘을 돌려 다항식 시간에 평문을 얻는다.
• Eve(도청자): 암호문 $c$만 가진다. 키 없이 평문을 복원해야 한다.

다만 이 닮음을 안전성의 증명으로 읽으면 안 된다. $P \neq \text{NP}$는 암호의 필요조건이지 충분조건이 아니다.

성립하는 방향부터 보자. $P = \text{NP}$라면 검증할 수 있는 것은 모두 풀 수 있으므로, 키를 가진 쪽만 빠르다는 이점이 사라지고 현대 암호는 무너진다. 이 방향은 옳다.

거꾸로는 성립하지 않는다. 이유는 셋이다.

• 최악의 경우와 평균의 차이. NP-난해함은 “어떤 입력에서는 어렵다”는 최악의 경우 진술이다. 암호는 키 생성기가 실제로 뽑는 분포 위에서 어려워야 한다. 어려운 입력이 몇 개뿐이고 나머지가 쉬운 문제는 암호가 되지 못한다.
• 다항식이 아니라는 것과 지수라는 것의 차이. $P \neq \text{NP}$는 다항식 시간 알고리즘이 없다는 말일 뿐이다. $n^{\log n}$처럼 어떤 다항식보다도 크면서 지수보다는 훨씬 작은 시간도 있다. “지수 시간 이상이 필요하다”는 결론은 여기서 나오지 않는다.
• 어느 문제가 어려운지는 말해주지 않는다. $P \neq \text{NP}$는 NP 안의 어떤 문제가 다항식 시간에 풀리지 않는다는 존재 진술이다. 내가 쓰는 암호를 깨는 문제가 그 어떤 문제인지는 별개다. 실제로 RSA가 기대는 정수 인수분해도, Diffie–Hellman이 기대는 이산 로그도 NP-완전이라고 알려져 있지 않다. 인수분해의 판정 버전은 NP와 coNP에 모두 속하는데, 이런 문제가 NP-완전이면 $\text{NP} = \text{coNP}$가 따라 나온다. 이 역시 참이라고 믿어지지 않는 등식이다.

그래서 암호의 안전성은 $P \neq \text{NP}$가 아니라 더 강하고 더 구체적인 가정 위에 선다. 인수분해가 어렵다, 이산 로그가 어렵다, 격자 문제가 어렵다 같은 개별 가정들이며, 이들은 하나같이 평균적 난이도를 요구한다.

키는 증명서가 아니다. 비유가 편해서 키를 증명서 $h$에 겹쳐 놓기 쉽지만 둘은 하는 일이 다르다. 검증자 $V$는 Yes/No를 내놓는 판정기이고, 복호화는 평문을 내놓는 함수다. 그리고 증명서는 "$x \in L$"을 뒷받침하는 것이지 아는 사람만 가질 수 있는 비밀이 아니다. 두 그림에서 겹치는 것은 “가진 쪽과 갖지 못한 쪽의 비용이 다르다”는 모양 하나뿐이다.

---

Df1과 Df2의 동치 증명

Df1 ⊆ Df2: NTM → 검증자

NTM $M$이 $x \in L$을 accept할 때, 계산 트리에서 accept에 이르는 경로가 하나 이상 존재한다.

그 경로 자체를 증명서 $h$로 사용한다.

• $M$이 다항식 시간 $p(n)$ 안에 동작하므로, accept 경로의 길이도 $p(n)$ 이하
• 검증자 $V$는 $h$로 지정된 경로를 따라 $M$을 시뮬레이션한다
• $M$이 accept하면 $V$는 Yes를 출력한다

따라서 $L \in \text{Df1} \Rightarrow L \in \text{Df2}$

Df2 ⊆ Df1: 검증자 → NTM

검증자 $V$와 다항식 $p$가 존재해 $x \in L \iff \exists h, |h| \leq p(|x|) : V(x,h) = \text{Yes}$라 하자.

NTM을 다음과 같이 구성한다:

1. 비결정론적으로 길이 $p(|x|)$ 이하의 모든 가능한 $h$를 열거한다
2. 각 $h$에 대해 $V(x, h)$를 실행한다
3. $V(x, h) = \text{Yes}$인 경우 accept한다

• $h$의 길이는 $p(|x|)$ 이하이므로, 가능한 후보의 수는 유한하고, NTM은 이를 비결정론적으로 선택할 수 있다
• $V$가 다항식 시간에 동작하므로, 전체 NTM도 다항식 시간 안에 동작한다

따라서 $L \in \text{Df2} \Rightarrow L \in \text{Df1}$

---

결론

	Df1 (NTM 기반)	Df2 (검증자 기반)
핵심 아이디어	모든 경로를 동시에 탐색	힌트가 있으면 빠르게 검증
직관	병렬 탐색	힌트의 비대칭성
증명서	암묵적 (경로 = 증명서)	명시적 (증명서 $h$)
동치 여부	두 정의는 완전히 동치	—