Introduction

앞에서 배운 대부분의 알고리즘은 polynomial time algorithm이다. input으로 주어지는 문제의 크기가 $n$이라면, worst case에서 $O(n^k)$의 시간이 걸리는 알고리즘이다. 세상에 존재하는 모든 문제들은 polynomial time algorithm으로 해결이 가능할까? 언제나 예외는 존재하듯, 모든 문제를 polynomial time algorithm으로 해결할 수 없다. Turing's Halting Problem이 그 대표적인 예시이다. 이번 시간에는 NP-Complete Problem에 대해 배워보자. NP 알고리즘의 정의는 Nondeterministic polynomial-time algorithm이다.

P, NP Classes

우선 세상에 존재하는 모든 문제들을 분류해보자. 간단하게 풀 수 있는(solvable), 풀 수 없는(unsolvable) 문제로 나눌 수 있을 것이다. 그런데 풀 수 있는(solvable) 문제들 중에서 polynomial time algorithm으로 풀 수 있는 문제들은 비교적 쉽게 풀리는 문제들이다. 예전에 polynomial time과 exponential time을 비교해보았을 때, polynomial time이 걸리는 알고리즘은 많은 시간이 소모되더라도 현실에서 충분히 감당할 수 있는 시간이 되지만, exponential time이 걸리는 알고리즘은 현실에서 감당할 수 없는 시간을 요구로 한다. 예를 들어 문제의 크기 $n=20$일 때, A 알고리즘이 $O(n^2)$이 걸린다면, 최악의 경우 400이다. 하지만, B 알고리즘이 A 알고리즘과 다르게 polynomial time이 걸리지 않고 exponential time, 예를 들면 $O(2^n)$이 걸린다면, 최악의 경우 $1,048,576$의 시간이 소모된다. 만약 문제의 크기가 20에 그치지 않고 200이라면 exponential time 알고리즘은 현실에서 해결되기에 힘들다. 이처럼 "polynomial time 내에 풀 수 있는 문제"들을 $\bf{P}$군(class)에 속한다고 정의한다. 그렇다면 $\bf{NP}$군은 polynomial time 내에 풀 수 없는 문제들을 의미할까? 아니다. $\bf{NP}$군의 정확한 정의는 "polynomial time 내에 확인할 수 있는 문제들"로 구성된다. 확인이라는 의미가 무엇일까? 영문으로는 verifiable을 의미한다. 즉, 해(solution)의 후보가 주어지면 문제 입력 크기에 대한 polynomial time내에 해당 후보가 올바른 해인지 확인할 수 있음을 말한다. $\bf{NP}$ 문제의 NP는 not polynomial time이 아니라 Nondeterministric Polynomial time의 약자임에 주의하자!

예를 들어 임의의 $\text{Set } = \{-2, 10, 4, -5, -3\}$에서 합이 0인 subset은 몇 개인가? 라는 문제를 풀려면 몇 가지의 경우를 확인해야 할까? 부분 집합의 개수를 생각해보면 $2^5 - 1$의 경우를 탐색해야 한다. 이는 exponential time 내에 해결되는 방법이다. 하지만, 주어진 subset에 대해 합이 0인가? 를 확인하는 문제는 polynomial time 내에 해당 해의 후보가 올바른 해인지 확인할 수 있는, $\bf{NP}$문제라 할 수 있다.

$\bf{P}$군(class)과 $\bf{NP}$군으로 문제들을 구분했을 때, $\bf{P}$군과 $\bf{NP}$군은 어떤 관계를 지닐까? $\bf{P}$군은 모두 $\bf{NP}군$에 속한다. 문제가 $\bf{P}$군에 속한다면, 후보가 주어지지 않더라도 문제를 polynomial time내에 풀 수 있기 때문이다. 즉, 다음이 성립한다.

물론, $\bf{P}$가 $\bf{NP}$의 진부분집합이라는 것은 아님에 유의하자.

NP-Complete

어떤 문제가 $\bf{NP}$에 속하고, $\bf{NP}$에 속하는 임의의 문제만큼 "어렵다(hard)"면 $\bf{NP\text{-Complete}}$군에 속한다고 한다. 그리고 이 문제를 $\bf{NP\text{-Complete}}$ 문제라고 한다. 엄밀한 정의는 없지만 다음과 같은 사실을 일단 받아들이자.

If any NP-complete problem can be solved in polynomial time, then every problem in NP has a polynomial-time algorithm

임의의 $\bf{NP-C}$ 문제 하나가 polynomial time내에 풀릴 수 있다면, 모든 $\bf{NP-C}$가 polynomial time algorithm을 가질 수 있다는 의미이다. 이렇게 말할 수 있는 이유는 누구도 $\bf{NP-C}$ 문제 중 하나에 대한 polynomial time algorithm을 구하지 못했다. 이처럼 $\bf{NP-C}$ 문제는 쉽게 풀 수 없는 문제라는 견해가 대부분이다. 하지만, 이 문제를 polynomial time 내에 풀 수 있다는 가능성을 완전히 배제할 수는 없다.

이런 $\bf{NP-C}$ 이론을 이해해야 하는 이유는 무엇일까? 회사 혹은 조직에서 해결하고자 하는 문제가 $\bf{NP-C}$군에 속하는 문제라 확증할 수 있다면, polynomial time내에 해결될 수 있는 알고리즘을 연구하는 비용보다 근사해를 구하는 알고리즘을 개발하거나 쉽게 풀리는 특별한 경우에 대해 연구하는 것이 더 효율적일 것이다. 이제 $\bf{NP-C}$ 이론을 이해해야 하는 이유를 배웠으니, 어떤 문제가 $\bf{NP-C}$임을 보이는 3가지 주요 개념에 대해 배워보자.

Decision Problem

우선 $\bf{NP-C}$문제는 decision problem에 대해서만 적용 가능하다. 그 이유는 decision problem은 어떠한 값이 해가 될 수 있는 지 "Yes" or "No"로 대답하는 문제이고, $\bf{NP}$문제는 polynomial time 내에 확인할 수 있는 문제이기 때문이다. 우리가 대부분 현실에서 관심을 갖게 되는 문제들은 optimization problem이다. 그런데 $\bf{NP-C}$문제는 decision problem에만 적용할 수 있으니 optimization problem과는 어떤 관련성이 있을까? 다음과 같은 예를 떠올려보자.

어떤 그래프 $G$와 정점 $u, v$가 주어질 때, 가장 적은 수 의 간선을 사용한 $u$에서 $v$까지의 경로를 찾는 문제가 있다고 하자. 이는 $\text{SHORTEST-PATH}$ 문제로 optimization problem이다. 하지만 $\bf{NP-C}$문제는 decision problem에만 적용가능하다고 하였다. 그런데 무방향 그래프 $G$와 정점 $u, v$, 정수 $k$가 주어졌을 때, k개 이하의 간선으로 구성되는 $u$에서 $v$의 경로가 존재하는지를 대답하는 $\text{PATH}$ 문제가 있다고 하자.

$\bf{NP-C}$문제가 decision problem에만 국한된다 할지라도 optimization problem과 decision problem 사이의 편리한 관계를 이용하면 $\bf{NP\text{-Completeness}}$과 optimization problem을 연관지을 수 있다.

즉, 주어진 optimization problem에서 최적화할 값에 한계를 부여함으로 이 문제와 관련된 decision problem으로 바꿀 수 있다. 그 예시가 바로 $\text{SHORTEST-PATH}$문제에 최적화할 값의 한계(정수 $k$)를 부여하여 $\text{PATH}$ 문제로 바꾼 것이다. optimization problem이 "어렵다"는 사실을 보이려고 할 때, 이 문제의 decision problem을 활용할 수 있다. $\text{SHORTEST-PATH}$ 문제를 polynomial time 내에 풀 수 있다면, $\text{PATH}$ 문제는 $\text{SHORTEST-PATH}$의 해로 나온 최적 경로의 간선 수와 $k$를 비교함으로 간단히 풀 수 있다. $\bf{NP\text{-Completeness}}$와 연관지어서 설명하면, decision problem이 "어렵다"면, 해당 optimization problem도 "어렵다"는 근거가 된다.

Reduction

어떤 문제가 다른 문제보다 어렵지 않다 또는 더 쉽지 않다는 것을 보이는 위의 개념은 두 문제가 모두 decision problem일 때도 적용할 수 있다. 거의 모든 $\bf{NP\text{-Completeness}}$ 증명에서 다음과 같은 아이디어를 적용한다. polynomial time 내에 풀고자 하는 decision problem을 $A$라고 하자. $A$의 입력 예를 $\text{instance } \alpha$라고 하자. 그런데 다른 decision problem $B$를 polynomial time내에 푸는 알고리즘을 알고 있다고 가정하자. 그럼 $\alpha \rightarrow \beta$로 변환하는 절차를 통해 $B$에 대한 yes or no라는 대답은 $A$의 답이 된다. 이때 변환하는 절차는 다음과 같은 특성을 가진다.

• 변환에는 polynomial time이 걸린다.
• 두 $\text{instance}$ $\alpha, \beta$의 답은 동일하다.

위 특성을 갖는 변환 절차를 polynomial-time Reducton Algorithm(환원 알고리즘)이라 한다. 위 절차를 통해 polynomial time 내에 $\alpha$에 대한 답을 내릴 수 있다. 즉, $A$를 푸는 것을 $B$를 푸는 것으로 "환원(reduction)"하여 $A$의 "쉬움"을 증명하기 위해 $B$의 "쉬움"을 이용한다. $\bf{NP\text{-Completeness}}$는 문제가 얼마나 쉬운지보다 어려운 지를 보이는 개념이였다. 한 문제가 $\bf{NP\text{-Completeness}}$임을 보이려면 위 reduction algorithm의 역과정을 이용한다. 즉, 어떤 문제 $A$가 어떠한 polynomial time algorithm으로 풀 수 없다는 사실을 안다고 하자. 그런데 위와 같은 polynomial time reduction algorithm이 존재한다면, $B$도 polynomial time algorithm을 가질 수 없다. 그 이유는 만약 $B$에 polynomial time algorithm이 존재한다면, reduction algorithm을 적용하여 $A$로 바꾼 다음 풀 수 있기 때문에, 최초의 전제($A$를 풀 수 있는 polynomial time algorithm이 없다.)가 모순이 된다.

First NP-Complete Problem

Reduction algorithm으로 어떤 문제가 $\bf{NP\text{-Completeness}}$임을 보이기 위해서는 이미 알려진 다른 $\bf{NP-C}$문제에 의존하게 된다. 그렇기에 "첫번째(First)" $\bf{NP-C}$문제가 필요하다. 이 첫번째 문제는 회로 만족 여부 문제(Satisfiability(SAT) problem)이다. 이는 다음 시간에 계속해서 알아보자.