NP-Completeness

상위 문서: 알고리즘 설계와 분석

개요

어떠한 문제에 대해 충분히 빠른 알고리즘을 찾지 못한 이유를 설명하고자 할때, 그 방식은 세 가지 중 하나이다:

1. 내가 문제를 잘 못풀어서. → 가오가 상함.
2. 해당 문제의 lower bound를 증명. → 지루하고 현학적임.
3. 내 잘못이 아니라, 세상의 그 누구도 풀 수 없는 문제다. → 간단함.

사실 어떤 문제를 해결하고자 할때, 이를 풀기 위한 다항시간 알고리즘을 찾을 수 없는 경우가 있다. 하지만 exponential-time lower bound 증명은 현재 기술로 거의 불가능하므로 이러한 문제들이 “진짜로 어려운지” 증명할 방법이 없었다. 하지만 Stephen Cook과 Richard Karp는 “어떤 문제가 다른 어려운 문제와 본질적으로 동일한 난이도를 가진다”는 개념을 만들었고, 이것이 바로 NP-completeness이다.

Problems

NP-Completeness에 대해서 서술하기 위해서는 먼저 문제(problem)가 무엇인지 정의해야 한다. 문제란 일반화된 질문(general question)으로서, 아래의 두 요소로 이루어져 있다:

1. 입력의 종류와 제약(Parameters of the input)
2. 무엇이 “정답”인지 조건을 명시한 것(conditions on a satisfactory answer)

즉, 입력과 출력의 조건을 정의한 것이 '문제'이다. 또한 인스턴스(instance)는 해당 문제의 구체적인 입력을 의미한다. 더 쉽게 말하면, 특정 입력값으로 완전히 명시된 문제이다. 예를 들어, 정렬 문제는 아래와 같은 입력과 출력을 가진다:

입력: $a_1,...,a_n$으로 이루어진 수열
출력: 해당 수열을 재배열하여 $a{\text{'}}_1\le a{\text{'}}_2\le ...\le a{\text{'}}_n$이 되도록 하는 것

이 경우, 인스턴스는 {3,5,2,7,4,8,1}과 같이 구체적으로 제시된 특정 순열이다. 또한 결정 문제(Decision Problems)는 답이 “예/아니오(yes/no)”로만 나오는 문제이다. 예를 들어 MST 문제는 출력이 "예/아니오"로 정의되지 않으므로 정렬 문제가 아니지만, "주어진 그래프 G와 정수 k에 대해 비용이 k 이하인 MST가 존재하는가?"는 결정 문제에 해당한다.
이때 NP-Completeness는 결정 문제에 대해 주로 적용되므로, 해당 문서에서의 모든 문제들은 결정 문제 형식으로 통일하여 다룬다.

Reduction

Reduction이란 주어진 문제를 다른 문제로 변환하여 푸는 것을 의미한다. 예를 들어 A라는 가상의 문제를 B를 이용하여 풀고 싶다면, 아래와 같은 절차를 따를 수 있다:

1. A(X)와 같이 인스턴스 X가 주어졌다고 가정하자.
2. X를 Y라는 B에 대한 인스턴스로 변환한다.
3. B(Y)를 풀면, 이를 A(X)의 답으로 사용할 수 있다.

이러한 과정 자체가 reduction이다. 이때 올바른 reduction이 진행되었다면, 변환이 수행되어도 정답이 변하지 않아야 한다. 이때 reduction을 잘 구성한다면 두 문제의 난이도를 비교할 수 있다. 이를 위해 아래와 같은 기본적인 가정이 필요하다.

X → Y를 변환하는 데 O(P(n)) 시간이 걸린다.
B(Y)은 O(P'(n'))의 시간 복잡도를 가진다. 
$\therefore$ A(X)는 O(P(n)+P'(n'))의 시간 복잡도를 가진다.

이때 n은 입력 인스턴스 X의 크기이며, P(n)은 변환 비용에 해당한다. 이때 중요한 것은 변환 비용 O(P(n))이 항상 다항 시간이라는 것이다. 이는 아래의 명제를 성립시킨다:

A → B이면 A$\le$p B 이며, B는 A보다 더 빨라질 수 없다.

이는 hardness 관점에서 A가 다항시간에 해결되지 않는 문제라고 할 때, B가 다항시간 내에 해결된다면 A 또한 다항 시간 내에 해결될 수 있기 때문이다. 따라서 주어진 문제 B가 다항시간에 해결되지 않는 것을 증명하기 위해서는 이미 다항시간 내에 해결될 수 없다는 것이 증명된 문제 A를 B로 A → B와 같이 reduction하여 해결할 수 있다.