[CM301] 11. P & NP

어려운 문제

 지금까지 우리는 다양한 알고리즘을 통해 그래프 탐색, 최단 경로, 최소 신장 트리 등 여러 문제를 해결하는 방법을 살펴보았습니다.

 어렵다고요? 흠,

 이제 우리는 문제가 ‘어렵다’는 것이 무엇인지 정의해야 할 때가 온 것 같네요.

 이때까지 우리가 살펴본 알고리즘들의 실행 시간을 되짚어봅시다. 너비 우선 탐색과 깊이 우선 탐색은 $O(V+E)$ 시간에 수행되며, 최단 경로를 찾는 다익스트라 알고리즘은 $O(E\log{V})$, 벨만-포드 알고리즘은 $O(VE)$시간 안에 최단 경로를 찾을 수 있었습니다.

 이들은 모두 공통점이 있죠. 바로 실행시간이 입력값(E 또는 V)에 대한 다항식으로 나타낼 수 있다는 점입니다. 이를 ‘다항 시간(polynomial time)안에 해결할 수 있다’라고 말합니다.

 그렇습니다. 모든 문제가 간단하게 해결되는 것은 아니었죠. 어떤 문제들은 입력의 크기가 조금만 커져도 계산 시간이 기하급수적으로 증가해버립니다. 이전 장에서 다루었던 순회 세일즈맨 문제(TSP)만 해도 $O(n^22^n)$의 시간, 즉 지수항이 들어가는 시간이 필요했습니다.

 이 정도 되면 나름 ‘어렵다’고 말해도 되지 않을까요?

 이렇게 우리는 문제를 푸는 데 걸리는 시간을 기준으로 문제가 어려운지 쉬운지를 판단할 수 있습니다. 다항 시간 안에 풀 수 있는 문제를 ‘쉬운 문제’로, 그렇지 않은 문제를 ‘어려운 문제’로 정해두는 식이죠.

 하지만 모든 문제들이 이렇게 간단하게 분류되어 동작하지는 않습니다. 우리가 어렵다고 생각하는 문제도 실은 명료한 풀이 방법이 아직 밝혀지지 않은 것일 수도 있고, 막상 정답이 주어졌을 때 정말 정답이 맞는지 판별하는 건 쉬울 수도 있거든요. 그렇다면 과연 무엇이 문제를 진정으로 어렵게 만드는 것일까요? 이런 어려운 문제들을 쉽게 해결하는 방법은 없을까요?

이 질문에 답하기 위해 계산 복잡도 이론(Computational complexity theory)이 등장하며, 그 핵심 개념 중 하나가 바로 P와 NP입니다.

 이제부터 P와 NP를 통해 문제들을 얼마나 복잡한가에 따라 분류하게 될 것입니다. 이를 통해 어떤 문제들이 본질적으로 ‘어려운지’를 살펴보도록 합시다.

P와 NP

결정 문제 (Decision Problem)

 본격적으로 들어가기에 앞서, 한 가지 정리가 더 필요합니다. 생각해보면, 이때까지 우리가 해결했던 문제들은 대부분 ‘가장 짧은 길이’, ‘가장 높은 값’과 같이 주어진 조건에서 최대, 혹은 최솟값을 구하는 이른바 최적화 문제였습니다.

 이러한 문제들은 직접적으로 복잡도를 비교하기가 어렵습니다. 그래서 계산 복잡도 이론에서는 문제를 예/아니오로만 답할 수 있는 형태로 바꾸어 다루는 경우가 많습니다. 이러한 문제를 결정 문제(decision problem)라고 합니다.

 예를 들어 순회 세일즈맨 문제(TSP)는 ‘모든 지점을 방문하는 최단 경로의 길이는 얼마인가?’라는 최적화 문제였죠. 이는 ‘모든 지점을 방문하는 길이가 k 이하인 경로가 존재하는가?’라는 결정 문제로 바꿀 수 있습니다. 여기서 입력값은 경로가 되고, 그에 따른 결과값은 ‘예’와 ‘아니오’ 둘 중 하나로만 나오게 됩니다.

 이렇게 문제를 결정 문제 형태로 표현하면, 서로 다른 문제들의 복잡도를 체계적으로 비교할 수 있습니다. 그러니까 이제부터 다루는 모든 문제는 예/아니오의 이지선다라고 생각하자고요.

P와 NP

 P와 NP는 결정 문제가 어떻게 풀리느냐에 따라 정의됩니다. 어떤 결정 문제가 P라면, 그 문제는 다항 시간 안에 해결(=예/아니오를 판단)할 수 있는 문제입니다.

 그리고 어떤 결정 문제가 NP라면, 그 문제는 다항 시간 안에…

 …판별할 수 있는 문제입니다.

 네, NP는 P의 반대 의미이지만 ‘풀 수 없는’ 문제가 아니라 ‘풀 수 있는지 모르는’ 문제거든요. 여기서 판별이라고 하면, 문제의 답이 ‘예’가 되는 입력값이 있을 때, 그 입력값에 대해 정말 답이 ‘예’인지 확인하는 절차입니다. 즉, 정답을 검토하는 작업인 셈입니다. 따라서 NP는 문제의 정답을 검토하는데 다항 시간이 걸리는 경우를 뜻합니다.

 NP문제는 보통 ‘조건을 만족하는 특정 x가 존재하는가?’와 같이 존재성(Existence)을 묻는 경우가 많습니다. 이런 문제의 답이 ‘예’인지 검토하기 위해서는 조건을 만족하는 단 하나의 x만 주어져도 되니까요.

 그렇다면 만약 어느 입력값에 대해서라도 ‘아니오’가 나올 수 밖에 없는 문제라면 어떨까요? 가령, ‘2로 나누어도 정수인 홀수 x가 존재하는가?’같은 경우요. 의외로 간단합니다. NP의 조건은 제시한 입력값이 정말 ‘예’가 나오는지 확인할 뿐이지, 문제에 반드시 ‘예’가 나오는 입력값이 있을 필요는 없거든요.

 만약 누군가가 정답 x를 들고 왔을 때, 우리는 단순히 x를 2로 나누어 정수인지 확인하면 될 뿐입니다. 다항시간 안에 검토할 수 있기 때문에, 이 문제는 NP라고 말할 수 있습니다. 네, 만약 그게 진짜 존재한다면요.

co-NP

  NP와 반대되는 개념으로 co-NP가 있습니다. 문제의 답이 ‘아니오’가 되는 입력값이 있을 때, 그 입력값에 대해 정말 답이 ‘아니오’인지를 다항 시간 안에 확인할 수 있다면 이는 co-NP라고 합니다.

 co-NP문제는 보통 ‘모든 x가 조건을 만족하는가?’와 같이 항진식(Tautology)과 관련된 경우가 많습니다. 이런 문제의 답이 ‘아니오’인지 검토하기 위해서는 조건을 만족하지 않는 단 하나의 x만 있어도 되니까요.

예시 - 자물쇠 따기

 여러분이 어떤 연유로 비밀번호를 모르는 잠금장치를 열어야 한다고 생각해봅시다. 한 칸 마다 0에서 9까지의 숫자가 들어갈 수 있는 다이얼이 n개 있는 이 잠금장치는 복잡한 전자 회로로 얽혀 있어 기계적 편법으로 각 자리의 숫자를 추론할 수 없도록 설계되어 있습니다. 이 경우 결정 문제는 ‘내 눈 앞의 자물쇠를 열 수 있는 비밀번호가 있는가?’가 되겠네요.

 단순하게 0…0 부터 9…9까지 하나씩 맞춰가며 자물쇠를 풀어보는 방법을 사용한다면, 자그마치 $O(10^n)$의 시간이 필요할 것입니다. 문제를 다항 시간 안에 풀 수 없으니, 이 문제를 P라고 하기에는 무리가 있죠.

 그런데, 당신이 자물쇠의 주인으로부터 비밀번호가 무엇인지 전해들었다고 해봅시다. ‘내 눈 앞의 자물쇠를 딸 수 있는가?’에 대한 답이 ‘예’라는 것을 알았고, 거기에 맞는 입력값까지 받은 것입니다. 이 비밀번호로 정말 자물쇠를 딸 수 있는지 확인하려면 어떻게 해야 할까요?

 네, 그냥 넣어보면 됩니다. 손쉽게 정답을 검토할 수 있으니, 자물쇠 문제는 NP라고 할 수 있습니다.

만약 잠금장치가 단순한 기계식이라면 어떻게 될까요? 이 때 각 다이얼은 서로에게 영향을 주지않고 독립적으로 동작합니다. 이런 경우 한 자리가 맞으면 ‘딸깍’ 소리가 난다던지, 어떠한 반응이 오게 되어 있죠. 그러니 우리는 각 자릿수가 맞을 때마다 그 값을 고정시키고 다음 값을 찾기를 반복하면 됩니다. 즉, 전체 문제를 부분으로 쪼개서 각개격파할 수 있는 셈입니다. 이런 경우 문제는 확실히 P라고 말할 수 있겠습니다.

P = NP?

 모든 결정문제는 P 문제이면 NP 문제이기도 합니다. 어떤 문제를 다항 시간 안에 풀 수 있다면, ‘예’를 내놓는 답도 다항 시간 안에 찾을 수 있으니 다항 시간 안에 검토할 수 있는 것이나 다름 없으니까요.

 그 반대도 마찬가지 입니다. ‘아니오’를 내놓는 답을 다항 시간 안에 찾을 수 있다면, 그것에 대한 검토도 다항 시간 안에 끝낼 수 있습니다. 그러니 P 문제이면 co-NP 문제라고도 할 수 있습니다.

 그렇다면… NP와 co-NP의 관계는? 둘은 서로 어떻게 포함되어 있을까요?

 이는 아직까지도 명확하게 해결되지 않은 문제입니다. 현재로서는 NP이면 co-NP인지, co-NP이면 NP인지, 혹은 둘 다 가능한지 정확히 알 수 없습니다. 이와 비슷한 맥락으로 NP이면 P인지, 즉 P=NP의 여부도 정확하게 밝혀지지 않았습니다. 이것들은 아직 열린 문제로 남아 있습니다.

 그 중에서도 P=NP가 시사하는 바는 특히 강력합니다. 제 아무리 풀기 복잡해보이는 문제가 있어도, 입력값에 대한 검토가 쉽다면 문제 자체를 간단하게 풀 수 있는 방법이 존재한다는 것을 알 수 있거든요. 이렇게 된다면 대부분의 최적화 문제들이 간단하게 해결될 수 있습니다. 물류 경로, 스케줄링, 회로 설계 등 다야한 분야의 문제들이 다항시간 안에 해결할 수 있는 알고리즘을 가질 것입니다.

 뿐만 아니라 오늘날 사용하고 있는 암호체계에도 타격을 줄 수 있습니다. 대부분의 암호체계는 입력값이 옳은 것인지 검증하는데 시간이 많이 걸리지 않으니까요. 그리고 이는 곧 암호키를 알아내는데 다항 시간이 걸릴 수 있음을 의미하게 됩니다.

 P와 NP의 정의만으로는 P=NP가 어째서 해결하기 어려운 난제인지 파악하기 충분하지 않습니다. 좀더 자세히 알아보기 위해서는 또 다른 개념들이 필요한데, 이는 다음 절에서 다루도록 하겠습니다.