우선 NP complete를 이해하기 위해 필요한 용어들을 먼저 정의한다.
Abstract problem $Q$란 instance set $I$ 와 solution set $S$사이의 binary relation 을 의한다.
예를 들어, 최단경로 문제의의 instance는 Graph와 두 개의 vertices 들로 이루어져 있을 수 있다. 여기서 우리는 solution이 yes or no 에 해당하는 Decision Problem에만 집중한다.
Decision Problem의 예시는 다음과 같다. 최단경로 문제 중 k step 안에 vertex u에서 vertex v로 가는 경로가 존재하는지를 묻는 문제를 PATH라고 할 때, instance $i= <G,u,v,k>$로 정의하며 , $PATH(i)=0 \; \text{or} \;1$이 된다.
class P
다항시간안에 풀 수 있는 문제를 의미한다. 수학적으로 $O(n^k))$라고 표현한다. 여기서 $n$은 문제의 input 사이즈를 의미하고 $k$는 상수이다.
이를 조금 더 엄밀하게 정의하기 위해 아래의 개념들을 소개한다.
Finite set of symbol $\Sigma$와 $\Sigma$의 원소들로 만들어진 문자열의 집합 language $L$을 생각해본다. 예를 들어 $\Sigma = \{ 0,1\}$ 이고 $L=\{10,11,101\}$ 이 될 수 있다.
Decision problem $Q$를 language $L$로 표현할 수 있다.
$$ L = \{x\in \Sigma^* | Q(x)=1 \} $$
이 때 알고리즘 $A$에 의해 accept 되는 language는 $L = \{ x \in \{0,1\}^* : A(x)=1\}$ 이다. 즉 $x\in L$이면 $A(x)=1$이다. 하지만 $x\notin A$라고 해서 꼭 $A(x)=0$이 되지는 않는다. 이에 해당하는 예시로 무한루프의 경우가 있다.
반면에 $x\notin A$에 대해서 모두 $A(x)=0$이면 $L$은 $A$에 의해 decide 된다고 표현한다.
Accepting 알고리즘은 존재하지만 Decision 알고리즘은 존재하지 않는 경우들이 있다.
이제 위의 정의들을 활용해 Complexity Class를 정의 할 수 있는데, complexity class P란,
$$P = \{ L \subset \{ 0,1\}^*. : \text{L을 다항시간안에 결정하는 알고리즘 A가 존재한다} \}$$을 의미한다.
class NP
다항시간안에 주어진 Certificate이 문제의 솔루션인지 확인할 수 있는 문제를 NP Problem 이라고 한다. 예를 들어 3-CNF 는 NP problem 이다.
여기서 우리는 $P \subset NP$ 임을 알 수 있다.
Reduction
$A$라는 decision problem의 instance $\alpha$ 를 $B$라는 decision problem의 instance $\beta$로 바꾸는 과정을 생각해본다.
$\beta$를 다항시간안에 풀 수 있다고 가정해본다.
1. 변환과정(Reduction)이 다항시간만큼 걸리고
2. $\alpha$와 $\beta$가 동일한 정답을 가질 때,
$A$와 $B$는 둘 다 쉬운 문제라고 결론 내릴 수 있다.
NP Complete
어떤 문제가 다른 모든 NP 문제만큼 어렵다면 NP complete 라고 한다.
위의 Reduction의 $A$와 $B$를 다시 생각해본다. $A$를 다항 시간 안에 풀 수 있는 알고리즘이 존재하지 않는다면, $B$를 다항시간 안에 풀 수 있는 알고리즘도 존재하지 않는다. 이는 귀류법으로 쉽게 증명할 수 있다. 즉, $A$가 NP-complete이면, $B$도 NP-complete이다.
이제 language $L_1$이 language $L_2$로 모든 \(x\in\Sigma^*\)에 대해 다항시간안에 reduction가능한 $f:\Sigma^* \rightarrow \Sigma^*$가 존재한다면, $ L_1 \leq_P L_2 $라고 표시를 한다. 즉 \( x\in L_1 \;\text{if and only if} \;f(x) \in L_2\) 인 것이다.
References
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.