[계산이론] #11. P-NP (2)

이전 글에서 어떤 문제가 $\textbf{P}$이고 어떤 문제가 $\textbf{NP}$인지 알아보았습니다. 이번 글에서는 이 두 집합 간의 관계에 대해 중점적으로 살펴보도록 하겠습니다.

 

P는 NP의 부분집합이다.

직관적으로 알 수 있듯, $\textbf{P}$는 $\textbf{NP}$의 부분집합입니다. 어떤 문제가 $\textbf{P}$라는 것은 그 문제의 정답을 Polynomial Time에 계산할 수 있다는 것인데, 이러면 당연히 어떤 정답이 진짜 정답인지 확인하는 것도 Polynomial Time에 가능하기 때문에 $\textbf{NP}$에 속하기 때문이죠.

 

EXP

지난 글에서 보았듯 $NPrime$ (2 이상의 정수 중 소수가 아닌 수를 이진법으로 나타낸 문자열의 집합)은 2002년에 $\textbf{P}$임이 증명되었습니다. 그러나 어떤 숫자가 합성수인지를 Polynomial Time에 판단하는 알고리즘은 여기서 설명하기에는 너무 어렵기 때문에, 조금 간소화된 알고리즘을 하나 알아보겠습니다.

if x = 0 or x = 1 then
	return YES and terminate
for a ← 2, x - 1 do
	if x mod a = 0 then
		return YES and terminate
return NO and terminate

이 알고리즘은 $x$가 합성수인지 아닌지를 판별합니다. $a$를 2부터 시작해 1씩 증가시키면서 $x$가 $a$로 나누어떨어지는지, 나누어떨어지지 않는지 확인합니다. 만약 $a$가 $x-1$까지 왔는데도 나누어떨어지는 경우가 없다면, $x$는 소수입니다. 그 전에 $x$가 $a$로 나누어떨어지면 $x$는 합성수겠죠.

이 알고리즘의 Running Time은 Exponential 입니다. 이렇게 Exponential Time에 해결할 수 있는 문제들이 여럿 있는데요, 조금 더 엄밀하게 다항식 $p$에 대해 $2^{p \left(n \right)}$ 시간 안에 해결할 수 있는 문제들의 집합을 정의할 수 있습니다. 이 문제들의 집합을 $\textbf{EXP}$ 라 부릅니다.

이 때 $\textbf{NP}$에 속하는 모든 Language는 Exponential Time에 해결 가능합니다. 즉, $\textbf{NP} \subset \textbf{EXP}$ 입니다. 이를 증명해보도록 하겠습니다.

먼저 $\textbf{NP}$에 속하는 임의의 Language $A$를 생각합시다. 그러면 $\textbf{NP}$의 정의에 따라, 아래를 만족하는 다항식 $p$와 언어 $B\in \textbf{P}$가 존재합니다.

$$\leq w\in A \Leftrightarrow \exists s:\left|s \right|\leq p\left ( \left|w \right| \right )\; and \; \left<w,s \right>\in B$$

이 때 어떤 문자열 $w$가 $A$의 원소인지 아닌지를 판단하는 아래의 알고리즘을 생각해 보겠습니다. 이 알고리즘은 문자열 $w$에 대한 모든 정답 $s$에 대해 $\left<w,s \right>$가 $B$의 원소인지 아닌지를 판별합니다.

이 알고리즘에서 for문의 반복 횟수는 $1+2+2^2+\cdots + 2^{p\left ( n \right )} \leq 2^{p\left ( n \right )+1}$ 입니다. 그리고 각 Loop는 Polynomial Time에 해결 가능하므로, 위 알고리즘 전체는 Exponential Time에 해결할 수 있다는 결론을 얻을 수 있습니다.

 

그럼 P=NP인가?

지금까지 $\textbf{P}$ 는 $\textbf{NP}$ 의 부분집합이며, $\textbf{NP}$ 는 $\textbf{EXP}$의 부분집합임을 보였습니다.

$\textbf{P}$는 $\textbf{NP}$의 부분집합이기는 하지만 $\textbf{P}=\textbf{NP}$인지 $\textbf{P}\nsubseteq \textbf{NP}$인지는 아직 밝혀지지 않았습니다. $\textbf{P}$와 $\textbf{NP}$가 같은지, 같지 않은지는 컴퓨터 과학에서 가장 중요한 문제 중 하나로 여겨지고 있습니다.

단, $\textbf{P} \neq \textbf{EXP}$임은 증명되어 있습니다. 그리고 $\textbf{NP}=\textbf{EXP}$인지 아닌지 역시 아직 밝혀진 바가 없습니다.

 

Non-Deterministic Algorithm (비결정론적 알고리즘)

저희는 지금까지 Deterministic Algorithm, 결정론적 알고리즘에 대해서만 다루었습니다. 이 알고리즘은 계산이 실행되는 동안 그 다음 단계가 이미 결정되어 있습니다. 그러나 비결정론적 알고리즘에서는 알고리즘이 실행되는 동안, 다음에 진행될 계산에 여러가지 가능성이 존재합니다.

예를 들어, $\left<a_1, a_2, \cdots, a_m, b \right>$가 $SOS$의 원소인지 아닌지 판단하는 알고리즘을 하나 설계해봅시다. 최대한 단순하게 생각해보겠습니다. 그러면 가능한 모든 경우의 수 $c_1, c_2, \cdots, c_m\in \left\{0,1 \right\}$에 대해 $\sum_{i=1}^{m}c_i a_i=b$가 성립하는 경우의 수가 존재하는지 판단하면 되겠죠.

이런 알고리즘은 결정론적 알고리즘입니다. 반면, 아래는 같은 기능을 하는 비결정론적 알고리즘입니다.

s ← 0
for i ← 1, m do
	s ← s or s ← s + a_i
if s = b then
	return YES
return NO

만약 $\left<a_1, a_2, \cdots, a_m, b \right>$가 $SOS$의 원소이면 위 알고리즘은 YES를 반환할 가능성이 있습니다. 반면 $SOS$의 원소가 아니면 위 알고리즘은 YES를 반환할 수 없고, 항상 NO를 반환할 것입니다.

즉, 비결정론적 알고리즘 $M$이 문자열 $w$를 받았을 때 적어도 하나의 Computation에서 YES를 반환할 경우 $M$이 $w$를 Accpet한다고 말합니다.

이 알고리즘의 Running Time은 Linear입니다. 이렇게 어떤 Language $A$를 Polynomial Time에 Decide하는 비결정론적 TM이 존재할 경우, $A$는 $\textbf{NP}$ 의 원소입니다. 이 역도 성립합니다.

 

감사합니다.

---

이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.