계산 복잡도 이론은 각 문제의 특성을 공부하는 학문입니다. 다음 두 가지의 문제를 비교해 봅시다.

• 정렬 문제: 주어진 $N$개의 정수를 정렬한 결과는 무엇인가?
• 부분 집합 합(subset sum) 문제: $N$개의 수가 있을 때 이 중 몇 개를 골라내서 그들의 합이 $S$가 되도록 할 수 있는가?

계산 복잡도 이론에서 문제의 난이도는 해당 문제를 해결하는 빠른 알고리즘이 있느냐를 나타냅니다. 여기서 빠른 알고리즘의 기준은 다항 시간 알고리즘입니다. 정렬 문제는 시간 복잡도가 $O(N log N)$인 퀵 정렬 알고리즘을 사용해 풀 수 있지만 부분 집합 합 문제는 완전 탐색 이외에 해결할 수 있는 알고리즘을 찾지 못했습니다. 따라서 모든 경우의 수를 계산해야하므로 지수 시간이 걸립니다.

문제의 분류

1. 다항식 시간 알고리즘을 찾은 문제

다항식 시간이 아닌 알고리즘도 있으나, 다항식 시간 알고리즘을 찾은 경우 이 분류에 속합니다.
예시로

• 정렬 문제: $O(N log N)$
• 정렬된 배열 검색 문제: $O(log N)$
• 행렬 곱셈 문제: $O(n^{2.3728639})$
• 최단경로 문제
• 최소 비용 신장 트리 문제
• 연쇄 행렬 곱셈 문제

가 있습니다. 이런 문제들을 P 문제라고 합니다.

2. 다루기 힘들다고 증명된 문제

비다항식 크기의 결과를 요구하는 비현실적인 문제들이 이 분류에 속합니다.
예시로 모든 해밀토니안 회로를 결정하는 문제가 있습니다. 모든 정점들 간에 이음선이 있다면 $(N-1)!$개의 답을 얻어야 하므로 비현실적입니다. 또한 SAT(충족 가능성 문제)도 시간 복잡도가 $2^n$으로 증명된 문제입니다.
결정 불가능한 문제도 이 분류에 속합니다. 문제를 풀 수 있는 알고리즘이 존재할 수 없다고 증명된 문제를 결정 불가능한 문제라고 합니다. 예로 종료 문제가 있습니다(프로그램이 얼마나 돌았는지는 종료까지 얼마나 남았는지와 상관없는 정보이기 때문에 종료까지 얼마나 남았는지 알 수 있는 방법이 없습니다).
요구가 현실적이나, 다항식 시간에 풀 수 없다고 증명된 문제도 이 분류에 속하지만 거의 없습니다.

3. 다루기 힘들다고 증명되지 않았고, 다항식 시간 알고리즘도 찾지 못한 문제

많은 문제들이 여기에 속합니다.
예시로

• 0-1 배낭 문제
• 순회 외판원 문제
• 그래프 색칠하기 문제
• 해밀토니안 회로 문제

등이 있습니다. 이런 문제들을 NP 문제라고 합니다.

최적화 문제와 결정 문제

최적화 문제란?

최적의 해를 찾는 문제입니다.
예시로, 그래프 G에서 길이가 가장 짧은 해밀토니안 경로는 얼마인지 구하는 문제가 있습니다. 좀 더 자세한 설명은 최적화 문제에 들어가면 있습니다.

결정 문제란?

대답이 "예" 또는 "아니오"로 제한된 문제입니다.
예시로, 그래프 G에서 길이가 k이하인 해밀토니안 경로가 존재하는지 구하는 문제가 있습니다.

어떤 최적화 문제에 대해서 다항식 시간 알고리즘이 있다면, 그 알고리즘으로부터 그 문제에 해당하는 결정 문제에 대한 다항식 시간 알고리즘을 쉽게 유추할 수 있습니다. 최적의 해를 찾으면 결정 문제는 당연히 해결할 수 있습니다. 왜냐하면 결정 문제를 $\log n$번 해결하면 최적화 문제도 해결할 수 있기 때문입니다. 예를 들어서 "노드 i부터 노드 j까지 길이 k이하인 경로가 있는가?"를 해결해서 만약 "예"라는 답을 얻으면 "그럼 $k\over 2$는?"이라고 물어볼 수 있고 나온 답에 따라 "그럼 $k\over 4$는?" 혹은 "$3k\over 4$는?" 이런 식으로 이분 탐색으로 물어보면 가장 길이가 짧은 경로의 길이를 얻을 수 있습니다. 따라서 P와 NP를 다룰 때 최적화 문제만 고려해도 됩니다. 최적화 문제를 다항 시간 안에 풀 수 있으면 결정 문제는 당연히 다항 시간 안에 풀 수 있기 때문입니다.

P와 NP의 정의

P 문제

P 문제란 다항식 시간 알고리즘이 존재하는 모든 결정 문제들의 집합입니다.

NP 문제

NP(Nondeterminisic Polynomial) 문제란 다항식 시간 비결정적 알고리즘으로 해결할 수 있는 모든 결정 문제의 집합입니다.
다항식 시간 비결정적 알고리즘이란 검증 단계가 다항식 시간인 알고리즘입니다. 즉, 결정 문제 자체를 해결할 수 있는 다항식 시간 알고리즘이 존재해야 함을 의미하지는 않습니다. 어떤 결정 문제를 풀 수 있는 다항식 시간 알고리즘을 찾을 수 없고, 다항식 시간 비결정적 알고리즘을 찾으면 그 결정 문제는 NP 문제에 속합니다. 여기서 비결정적 알고리즘이란 같은 입력이 주어지더라도 실행될 때마다 다른 행동을 취하는 알고리즘을 말합니다.

환산

계산 복잡도 이론에서 두 문제의 난이도를 비교하기 위해 환산이라는 기법을 이용합니다. 환산이란 한 문제를 다른 문제로 바꿔서 푸는 기법입니다.

A의 입력을 적절히 변형해 B의 입력으로 바꾸는 환산 알고리즘이 존재한다고 합시다. 이때 B를 푸는 가장 빠른 알고리즘을 가져오면, 이것을 환산 알고리즘과 결합해 A를 푸는 알고리즘을 만들 수 있습니다. 환산 알고리즘이 무시할 수 있을 정도로 빠르다고 가정하면 결합된 알고리즘은 B를 푸는 가장 빠른 알고리즘과 같은 시간이 걸릴 겁니다. A를 푸는 가장 빠른 알고리즘은 앞에서 결합된 알고리즘과 같거나 더 빠를 테니, 결국 A를 푸는 가장 빠른 알고리즘은 B를 푸는 가장 빠른 알고리즘과 같거나 더 빠를 수밖에 없습니다. 이 경우 B가 A이상으로 어렵다는 것을 알게 됩니다.
만약 문제 A를 다항식 시간 내에 풀 수 없다는 것이 증명되면 문제 B 또한 다항식 시간 내에 풀 수 없습니다. 귀류법을 적용해 생각해보면 문제 B를 다항식 시간 내에 풀 수 있다면 문제 A 또한 다항식 시간 내에 풀 수 있어야 하는데 문제 A를 다항식 시간 내에 풀 수 없다는 것이 증명이 되었다는 사실과 모순되므로 문제 A를 다항식 시간 내에 풀 수 없다는 것이 증명되면 문제 B 또한 다항식 시간 내에 풀 수 없습니다. 여기서 주의해야 할 점은 "문제 A를 다항식 시간 내에 풀 수 있다면 문제 B도 다항식 시간 내에 풀 수 있다"라는 명제는 거짓입니다.

다항식 시간 변환의 예

그래프 $G$에 해밀토니안 사이클이 존재하는지 알려면 TSP문제로 바꿔서 해결하면 알 수 있습니다. $G$를 완전 그래프로 바꾸고 완전 그래프로 바꿀 때 원래 존재하지 않던 에지의 가중치는 2, 존재하던 에지의 가중치는 1로 설정하고 TSP 문제를 풀었을 때 만약 TSP 문제의 답의 길이가 모든 노드의 개수과 같다면 해밀토니안 사이클이 존재하고 그렇지 않다면 존재하지 않는 것입니다. TSP 알고리즘은 최대한 가중치가 작은 경로를 선택해서 사이클을 만들려고 하는 알고리즘인데 가중치가 더 큰 경로를 선택했다는 것은 가중치가 더 작은 경로를 선택해가지곤 사이클을 만들 수 없다는 뜻이기 때문입니다. 따라서 TSP문제는 해밀토니안 사이클 문제보다 더 어렵고, TSP 문제를 다항 시간 안에 해결할 수 있다면 해밀토니안 사이클 문제도 다항 시간 안에 해결할 수 있습니다.

NP-완전

어떤 문제 B가 NP에 속하고 NP에 있는 모든 문제 A에 대해 $A\le p B$(p는 환산 알고리즘의 시간입니다)라면 문제 B는 NP-완전입니다. 문제 B만 다항식 시간에 풀 수 있으면 NP에 속한 모든 문제들을 다항식 시간에 풀 수 있으므로 문제 B는 NP 집합에서 가장 어려운 문제입니다.

NP-난해

어떤 문제 A에 대해서, 만일 모든 NP문제가 문제 A로 다항식 시간에 변환이 가능하다면, 문제 A는 NP-난해 문제입니다. NP-완전과의 차이점은 NP-완전은 결정 문제만 포함하지만 NP-난해는 결정 문제가 아닌 문제도 포함합니다. 즉, 최적화 문제도 포함합니다.

NP-난해 문제 중 하나를 다항 시간에 풀 수 있다면, 이 알고리즘을 이용해 NP에 속한 모든 문제를 다항 시간에 풀 수 있습니다. 하지만 NP-난해 문제를 다항 시간에 풀려고 하는 것은 매우 어려운 일이므로 모델링을 달리 하거나, 근사해를 찾는 등 다른 방법을 찾는 것이 합리적일 것입니다.

P, NP, NP-완전의 관계

둘 중 뭐가 맞는지 인간은 아직 증명하지 못했습니다.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)