세상의 문제
모든 문제들은 "해결할 수 있는 문제인가?" 와 "해결할 수 없는 문제인가?"라는 두 가지의 집합으로 나눌 수 있다. 해결할 수 없는 문제의 대표적인 경우가 앨런 튜닝이 증명한 정지 문제가 되겠다. 해결할 수 없는 문제는 다시 "현실적인 시간 안에 풀 수 있는 문제" 와 "현실적인 시간 안에 풀 수 없는 문제"로 나눌 수 있다.
지금까지 공부한 알고리즘들은 모두 다항식 시간이 걸리는 문제들이었다. 예를 들어, \(O(n^2)\)의 시간이 필요한 선택 정렬, \(O(nlogn)\)의 시간이 필요한 병합 정렬, \(O(n^3)\)의 플로이드-워셜 알고리즘, ... 등이 있었다. \(O(nlogn)\)은 다항식은 아니지만, \(O(n^2)\)에 속하기 때문에 다항식 시간에 속한다고 볼 수 있다. 이들이 현실적인 시간 안에 풀 수 있는 문제이다. 반대로, \(O(n!)\)이거나 \(O(n^r)\)같은 다항식 시간에 속하지 않는 문제들이 있다. 이들을 현실적인 시간에 풀 수 없는 문제라고 한다.
NP-완비는 이 "현실적인 시간 안에 풀 수 없는 문제" 이면서도 서로 논리적 연관성을 지니는 문제군들을 말하는 것이다. 여기서 말한 논리적 연관성은, NP-완비군에 속하는 문제 중 단 하나라도 다항식 시간에 해결된다면, 모든 NP-완비군에 속하는 문제가 다항식 시간에 해결가능한 문제가 된다는 것이다.
Yes or No 문제와 최적화 문제
아마, 모든 문제들에 대한 답은 두가지로 나눌 수 있을 것이다. "맞다/아니다"와, "가장 적합한 답". 예를 들어 매우 간단하겠지만, "2차원 배열에서 가장 작은 원소를 찾을 방법이 있는가?" 라는 문제라면 Yes나 No로 답하는 문제이다. 그에 반해, "2차원 배열에서 가장 작은 원소는 무엇인가?" 라고 묻는다면 그에 대한 적절한 원소를 답해야한다.
NP
그럼 NP-완비의 NP는 무슨 의미일까. P는 다항식 Polynomial의 앞글자로, 다항식 시간에 풀 수 있는 문제군을 말한다. 그럼 NP는 Non Polynomial 이라고 해서 다항식 시간에 풀 수 없는 문제군을 뜻하는 것일까? 그렇지 않다. NP는 Nondeterministic Polynomial으로 비결정론적 다항식 시간에 풀 수 있는 문제군이라는 뜻이다. 그런데 비결정론적이 무슨 의미지?? 더 쉽게 이해해보자.
위 단락에서 말한 Yes or No로 답하는 문제를 보고 결정 문제(Decision problem)이라고 한다. 이 결정 문제를 다항식 시간에 풀 수 있는 문제들의 집합을 P라고 한다. 다르게 말하면, P는 Yes나 No라는 답을 다항식 시간에 낼 수 있는 문제군이다. NP는 문제의 답이 Yes라는 근거가 주어지면 그것이 옳다는 것을 다항식 시간에 증명해줄 수 있는 문제이다. 그러니, P는 NP에 속한다. 즉, P는 NP의 부분집합이다.
비결정론적 다항식 시간 쉽게 이해하기
다음과 같은 그래프와 정점들이 주어진다고 하자. 정점 S에서 F까지 가능 경로를 찾는다고 한다.
한 정점을 방문하는 시간을 1이라고 하자. 그렇다면 결정론적인 관점으로는 최선의 경우 2의 시간이, 최악의 경우 6의 시간이 필요하다. 결정론적 관점에서는 풀이 과정에서 거친 모든 과정이 시간에 반영이 된다.
비결정론적 관점은 그렇지 않다. 위의 문제는 비결정론적인 관점에서는 2의 시간이 소요된다. 답을 구하는데 든 시행착오는 고려하지 않았기 때문이다. 2의 시간이 소요되는 경로가 있다는 답을 가지고, 그것이 맞다는 것을 증명하는데 걸린 시간이 2라는 것이다.
다항식 시간 변환
결정문제 A가 있다. A를 다항식 시간에 해결할 수 있는지를 알고 싶은데, 다항식 시간에 해결 가능한 결정 문제 B가 있다고 한다. A를 다항식 시간에 B로 변형할 수 있고, 그 결과 B의 해답과 A의 해답이 항상 일치한다고 가정한다면 A도 다항식 시간에 문제를 해결할 수 있다.
예를 들어, G = (V, E) 라는 무방향 그래프에서 해밀턴 사이클(Hamiltonian Cycle)이 존재하는가? 라는 문제가 있다고 하자.
무방향 그래프 \(G = (V, E)\)에 대하여, 해틸턴 사이클이 존재하는가?
외판원 문제(TSP : Traveling Salesman Problem)는 가중치가 있는 완전 그래프에서 길이가 가장 짧은 해밀턴 순환을 찾는 문제이다.
양의 가중치를 가진 무방향 완전 그래프 (\G = (V,E)\)에 대하여, 길이가 \(k\)이하인 해밀턴 사이클이 존재하는가?
해밀턴 사이클을 찾는 문제를 A, TSP를 찾는 문제를 B로 한다. 그럼 아래와 같이 변환해서 해결할 수 있다.
4이하의 해밀턴 사이클이 존재하는가? 라는 문제로 바뀌었다. TSP를 다항식 시간에 풀 수 있는 알고리즘이 있다면 해밀턴 사이클도 다항식 시간에 풀 수 있게 된다.
NP-난해(NP-Hard)
NP-완비인 문제들은 NP-난해에 포함된다. NP-난해의 정의는 아래와 같다.
모든 NP문제 \(L\)에 대하여, \(L \le _p A\)이면 \(A\)는 NP-난해 문제이다.
위 정의에서 \(\le _p\)는 다항식 시간 변환을 말한다. NP의 모든 문제가 \(A\)로 변환이 가능하면 \(A\)는 NP-난해 문제인 것이다. NP-난해의 대표적인 예시가 위에서도 언급한 정지 문제이다. 그런데, 이 정지 문제는 NP-완비 문제는 아니다.
NP-완비(NP-Complete)
NP-완비는 위의 NP-난해의 정의에서 한가지가 더 추가된다.
\(A\)는 NP이다.
즉, NP-완비에 속하는 문제는 NP문제 이면서도 NP-난해 문제이다. 그러니까, NP-완비 문제는 NP의 부분집합 이면서 NP-난해의 부분집합인 것이다.
P＝NP ? P ≠ NP ?
위에서 P문제는 NP문제의 부분집합이라고 했다. NP-완비에 속하는 문제 중 하나라도 다항식 시간에 해결가능하게 된다면 모든 NP-완비 문제가 다항식 시간에 해결가능하게 된다고도 했다. NP-완비의 정의를 보면, NP-완비군의 문제 중 단 하나라도 다항식 시간에 해결할 수 있게 된다면 모든 NP 문제에 대해 P = NP가 될 것이다. 그러나, NP-완비군의 문제 중 단 하나라도 불가능함이 밝혀진다면 P ≠ NP 가 될 것이다.
P＝NP 인지 P ≠ NP 인지에 대한 해답은 아직까지도 밝혀지지 않았다. 미국의 클레이 연구소에서 각각 100만 달러의 현상금(?)을 걸고 만든 7개의 난제인 밀레니엄 문제(Millennium Prize Problem)중 하나이기도 하다.
[Reference]
문병로, 「쉽게 배우는 알고리즘」 (한빛 아카데미, 2018)
'알고리즘(Algorithm) > Algorithm' 카테고리의 다른 글
| [알고리즘] 그리디 알고리즘 (Greedy Algorithm) (0) | 2022.04.12 |
|---|---|
| [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) (0) | 2022.04.11 |
| [알고리즘] 동적 계획법(Dynamic Programming) (0) | 2022.04.05 |
| [알고리즘] 최소 신장 트리(Minimum Spanning Tree) (0) | 2022.04.04 |
| [알고리즘] 너비 우선 탐색(BFS) / 깊이 우선 탐색(DFS) (0) | 2022.04.04 |