NP-Completeness 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[알고리즘 설계와 분석#NP-Completeness|알고리즘 설계와 분석]] 

==개요==
어떠한 문제에 대해 충분히 빠른 알고리즘을 찾지 못한 이유를 설명하고자 할때, 그 방식은 세 가지 중 하나이다:
# 내가 문제를 잘 못풀어서. → 가오가 상함.
# 해당 문제의 lower bound를 증명. → 지루하고 현학적임.<ref>하지만 일반적인 문제에 대해 lower bound 증명은 극도로 어렵다.</ref>
# 내 잘못이 아니라, 세상의 그 누구도 풀 수 없는 문제다. → 간단함.
사실 어떤 문제를 해결하고자 할때, 이를 풀기 위한 다항시간 알고리즘을 찾을 수 없는 경우가 있다. 하지만 exponential-time lower bound 증명은 현재 기술로 거의 불가능하므로 이러한 문제들이 “진짜로 어려운지” 증명할 방법이 없었다. 하지만 Stephen Cook과 Richard Karp는 “어떤 문제가 다른 어려운 문제와 본질적으로 동일한 난이도를 가진다”는 개념을 만들었고, 이것이 바로 NP-completeness이다.

==Reduction==
Reduction이란 주어진 문제를 다른 문제로 변환하여 푸는 것을 의미한다. 예를 들어 A라는 가상의 문제를 B를 이용하여 풀고 싶다면, 아래와 같은 절차를 따를 수 있다:
# A(X)와 같이 인스턴스 X가 주어졌다고 가정하자.
# X를 Y라는 B에 대한 인스턴스로 변환한다.
# B(Y)를 풀면, 이를 A(X)의 답으로 사용할 수 있다. 
이러한 과정 자체가 reduction이다. 이때 올바른 reduction이 진행되었다면, 변환이 수행되어도 정답이 변하지 않아야 한다. 이때 reduction을 잘 구성한다면 두 문제의 난이도를 비교할 수 있다. 이를 위해 아래와 같은 기본적인 가정이 필요하다. 
 X → Y를 변환하는 데 O(P(n)) 시간이 걸린다.
 B(Y)은 O(P'(n'))의 시간 복잡도를 가진다. 
 <math>\therefore</math> A(X)는 O(P(n)+P'(n'))의 시간 복잡도를 가진다.
이때 n은 입력 인스턴스 X의 크기이며, P(n)은 변환 비용에 해당한다. 이때 중요한 것은 변환 비용 O(P(n))이 항상 다항 시간이라는 것이다. 이는 아래의 명제를 성립시킨다:
 A → B이면 A<math>\le</math>p B 이며, B는 A보다 더 빨라질 수 없다.
이는 hardness 관점에서 A가 다항시간에 해결되지 않는 문제라고 할 때, B가 다항시간 내에 해결된다면 A 또한 다항 시간 내에 해결될 수 있기 때문이다. 따라서 주어진 문제 B가 다항시간에 해결되지 않는 것을 증명하기 위해서는 이미 다항시간 내에 해결될 수 없다는 것이 증명된 문제 A를 B로 A → B와 같이 reduction하여 해결할 수 있다.

==각주==