NP 이론
1. \(P = NP\) ?
1) 결정문제(decision problem)
- 출력이 단순히 yes 또는 no인 문제를 결정문제라 한다. 최적해를 구하는 모든 문제는 그에 상응하는 결정문제가 있다. 예를 들어 TSP 문제는 ‘주어진 경로보다 더 짧은 여행경로가 있는가?’ 라는 결정문제로 대응된다.
- 결정문제 중, 다차시간 알고리즘으로 풀 수 있는 모든 결정문제 집합을 흔히 P라 칭한다.
2) 비결정적 알고리즘(nondeterministic algorithm)
- 비결정적 알고리즘은 (1)해를 추측으로 제시하는 단계와 (2)이를 검증하는 단계로 구성된 알고리즘을 말한다. 예를 들어, TSP 결정문제에 대해 yes라 답하며 그 해(여행경로)를 제시한다 할 때(추측 단계) 그것이 올바른 경로인지를 검증(검증 단계)하는 알고리즘을 생각할 수 있다.
- 비결정적 알고리즘의 추측 단계는 그 알고리즘이 단계별로 제시되지 않으며, 이처럼 알고리즘이 단계별로 제시되지 않는 것을 비결정적(nondeterministic)이라 한다.
3) NP 집합
- 비결정적 알고리즘 중 검증 단계가 다차시간인 알고리즘을 다차시간 비결정적 알고리즘(polynomial-time nondeterministic algorithm)이라 한다.
- 다차시간 비결정적 알고리즘으로 풀 수 있는 모든 결정문제 집합을 흔히 NP(nondeterministic polynomial)라 한다.
- 비결정적 알고리즘으로 풀리는 문제 중, 그 추측 단계를 다차시간으로 풀 수 있는지 증명되지 않은 문제들이 있다. (이를 흔히 NP문제라 한다.) 만약 이 문제들이 다차시간으로 풀 수 있다고 증명된다면, \( P = NP \)라고 쓸 수 있을 것이다. 그러나 이 문제들이 다차시간으로 풀 수 있는지 없는지는 아직 증명되지 않았으므로, \(P = NP\) 인지 \(P \ne NP \) 인지는 아직 알지 못한다.
- TSP 결정문제는 대표적인 NP 문제다. TSP 문제의 추측 단계에서 최적 여행경로를 다차시간 내에 제시할 수 있는지 없는지는 아직 증명되지 않았다.
2. NP-complete
1) 변환(transformation) 알고리즘
- 두 결정문제 A, B가 있고 여기서 A는 푸는 알고리즘을 모르지만 B는 푸는 알고리즘을 알고 있으며 이 알고리즘이 \(x_i\)라는 입력에 대해 \(y_i\) 라는 출력을 낸다고 하자. 한편 문제 A가 \(y_i\)라는 같은 출력을 내기 위한 입력이 \(z_i\)라 할 때, 모든 \(z_i\)에 대해 이에 대응되는 \(x_i\)를 찾아내는 알고리즘을 쓸 수 있다고 하자. 이때 이 알고리즘을 결정문제 A를 결정문제 B로 변환하는 변환 알고리즘이라 한다.
2) 다차시간 다일 축소가능(polynomial-time many-one reducible)
- 결정문제 A를 결정문제 B로 다차시간 안에 변환하는 알고리즘이 존재한다면 이를 두고 ‘문제 A가 문제 B로 다차시간 다일 축소가능하다’라고 한다.
- 결정문제 B가 P 집합에 속한다면 결정문제 A도 P 집합에 속한다. 변환 알고리즘의 시간복잡도가 \(p(n)\)이고 B를 푸는 알고리즘의 시간복잡도가 \(q(m)\)이라면 A를 푸는 알고리즘의 시간복잡도는 \(p(n) + q(p(n))\)이 되어 다차시간 시간복잡도를 갖기 때문이다.
3) NP-complete
- 어떤 결정문제가 모든 NP인 결정문제로부터 다차시간 다일 축소가능하면 그 결정문제를 두고 NP-complete라 한다.
- 어느 한 NP-complete 문제라도 P 집합에 속함이 증명된다면 P = NP임이 증명되는 것과 같다.
- NP-complete인 어떤 결정문제 A가 어떤 결정문제 B로 다차시간 다일 축소가능하면 이 결정문제 B 또한 NP-complete이다.