참고: 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)
문제의 특성
계산 복잡도 이론은 각 문제의 특성을 공부하는 학문이다. 다음 두 문제에 대해 살펴보자.
- 정렬 문제: 주어진 $N$개의 정수를 정렬한 결과는 무엇인가?
- 부분 집합 합(subset sum) 문제: $N$개의 수가 있을 때 이 중 몇 개를 골라내서 그들의 합이 $S$가 되도록 할 수 있는가?
이 때 각 문제의 난이도는 문제를 풀 때의 난이도가 아니다. 계산 복잡도 이론에서 문제의 난이도는 문제를 풀 때의 난이도가 아니라 해당 문제를 해결하는 빠른 알고리즘이 있느냐를 나타낸다. 빠른 알고리즘이 있는 문제는 계산적으로 쉽고, 그렇지 않은 문제는 계산적으로 어렵다고 말한다. 그렇다면 ‘빠른’ 알고리즘이란 무엇일까? 일반적으로 다항 시간 알고리즘이나 그보다 빠른 알고리즘들만을 ‘빠르다’고 말한다.
계산 복잡도 이론에서 이렇게 다항 시간 알고리즘이 존재하는 문제들의 집합을 P 문제라고 부른다. P 문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합을 계산 복잡도 클래스(complexity class)라고 부른다. 그 중 중요한 것이 P, NP 문제이다.
난이도의 함정
그러나 어떤 문제를 다항 시간에 풀 수 있음을 증명하기는 쉽지만, 풀 수 없음을 보이기란 어렵다. 따라서 다항 시간 알고리즘이 존재하는 문제와 존재하지 않는 문제로 문제들을 구분하기엔 어렵다. 계산 복잡도에서 흔히 말하는 ‘어려운 문제’들은 다음과 같이 정의된다.
- 정말 어려운 문제를 잘 골라서 이것을 어려운 문제의 기준으로 삼는다.
- 앞으로는 기준 문제만큼 어렵거나 그보다 어려운 문제들 즉, ‘기준 이상으로 어려운 문제들’만을 어렵다고 부른다.
하지만 이 기준에 따라 문제를 분류하려면 난관에 부딪힌다. 주어진 문제가 기준 이상으로 어려운지 판정하기가 쉽지 않기 때문이다. 문제 A가 문제 B 이상으로 어렵다고 말하려면 A를 푸는 가장 빠른 알고리즘이 B를 푸는 가장 빠른 알고리즘 이상의 시간이 걸려야 한다. 그러나 대부분의 경우 우리는 문제를 푸는 가장 빠른 알고리즘이 무엇인지 모른다.
계산 복잡도 이론에서는 두 문제의 난이도를 비교하기 위해 환산(reduction)이라는 기법을 사용한다. 이는 한 문제를 다른 문제로 바꿔서 푸는 기법이다. B의 입력을 변형해 A의 입력으로 바꾸는 환산 알고리즘이 존재하면 A를 푸는 가장 빠른 알고리즘으로 B를 해결하는 알고리즘을 만들 수 있다. 환산 알고리즘의 실행 시간이 무시할 수 있을 정도로 빠르다고 하면 결합된 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같은 시간이 걸릴 것이다. B를 푸는 가장 빠른 알고리즘은 이 결합된 알고리즘과 같거나 더 빠를 것이다. 결국 B를 푸는 가장 빠른 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같거나 더 빠를 수 밖에 없다. 즉 A가 B 이상으로 어렵다는 것이다.
NP 문제, NP 난해 문제
문제의 난이도를 비교할 수 있으니 어려운 문제의 기준을 정해야 한다. 이 때 어려운 문제의 기준이 되는 것이 바로 SAT 문제(satisfiability problem)이다. SAT 문제란 $N$개의 boolean 값 변수로 구성된 논리식을 참으로 만드는 변수 값들의 조합을 찾는 문제이다. SAT 문제는 모든 NP 문제 이상으로 어렵다.
NP 문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미한다. 모든 P 문제들은 NP 문제에도 포함된다. SAT가 모든 NP 문제 이상으로 어렵다는 것은 SAT를 다항 시간에 풀 수 있으면 NP 문제들을 전부 다항 시간에 풀 수 있다는 말과 동일하다. 이런 속성을 갖는 문제들의 집합을 NP-난해(NP-Hard) 문제라고 부른다. NP-난해 문제들은 아직 다항 시간에 푸는 방법이 발견되지 않았다.
NP-난해 문제이면서 NP인 문제들을 NP-완비(완전) 문제라고 한다.
P=NP
P=NP 문제는 P와 NP가 같은지를 확인하는 문제이다. NP-난해 문제 중 하나를 다항 시간에 풀 수 있다면 이 알고리즘을 이용해 NP에 속한 무든 문제를 다항 시간에 풀 수 있다. 이 경우 NP에 속한 모든 문제를 다항 시간에 해결할 수 있으므로 P=NP임을 알 수 있다. 반대로 NP문제 중 하나를 골라 다항 시간에 푸는 방법이 없음을 증명하면 P$\neq$NP임을 보일 수 있다. 이 문제는 아직까지 미해결 문제이다.