P-NP 문제

밀레니엄 문제중 하나인 P-NP 문제는 컴퓨터 전공자가 아닌 사람들에게도 꽤나 잘 알려진 문제입니다. P가 NP의 진부분집합인지 아닌지를 증명하는 100만 달러가 걸린 문제인데, 수십년동안 아무도 풀지 못했습니다. 이 문제는 컴퓨터 과학의 한 갈래인 계산 이론(Theory of computation)과 관련이 있는 문제인데, 계산 이론은 어떤 문제를 컴퓨터(알고리즘)로 풀 수 있는지 없는지, 풀 수 있다면 쉬운 문제인지 어려운 문제인지를 탐구하는 분야입니다. 아래의 내용은 계산 이론과 P-NP 문제에 대해 제가 공부한 내용을 정리한 것입니다. 저도 공부하는 입장이기 때문에 잘못된 내용이 있을수도 있습니다. 혹시 오류가 있다면 지적해주시면 감사하겠습니다.

---

1. 결정 문제 (Decision problem)

결정 문제란 여러 문제들 중 Yes or No로 답이 나오는 문제를 의미합니다.

가령 "두 정수 x, y가 있을 때 x는 y로 나누어 떨어지는가? ” 라는 문제는 x와 y의 값에 따라 Yes or No로 답이 나오기 때문에 결정 문제입니다. 반면에 “두 정수 x, y가 있을 때 x를 y로 나눈 나머지는 무엇인가?” 라는 문제는 x와 y의 값에 따라 숫자로 답이 나오기 때문에 결정 문제가 아닙니다. 계산 이론에서는 일반적으로 결정 문제만을 다룹니다. 따라서 P집합과 NP집합도 결정 문제들의 집합입니다. 그렇다면 왜 하필 결정 문제일까요? 이유는 다른 종류의 문제와 비교했을 때 결정 문제가 상대적으로 단순하고, 결정 문제가 아닌 많은 문제들이 결정 문제로 변환될 수 있기 때문입니다. 가령 최적화 문제인 Traveling salesman problem(외판원 문제)를 예로 들어보면

TSP(G) = 그래프 G에서 모든 정점을 지나는 사이클 중 가장 가중치가 낮은 것

이라는 최적화 문제를

TSP_Decision(G, K) = 그래프 G에 모든 정점을 지나는 가중치가  K이하인 사이클이 존재하는가?

이렇게 결정 문제로 변환할 수 있습니다.

최적화 문제에 다항시간 알고리즘이 존재한다면, 당연하게도 그 문제에 대응하는 결정문제 또한 당연히 다항시간 알고리즘이 존재합니다. 놀랍게도 많은 경우 이 역도 성립합니다. 즉 많은 경우에 결정문제에 대한 다항시간 알고리즘을 통해 최적화 문제에 대한 다항시간 알고리즘도 만들 수 있습니다. 결정 문제를 해결하는 알고리즘에 바이너리 서치를 적용하는 Parametric search라는 테크닉을 통해 최적화 문제를 해결할 수 있습니다. 위의 TSP문제로 예를 들어보면 만약 TSP_Decision(G, K)를 다항시간에 해결할 수 있다면 바이너리 서치를 통해 K값을 바꾸어가며 TSP_Decision(G, K)를 log N번 실행하여 최적값을 구할 수 있습니다. 코드로 예시를 보이자면

int TSP(Graph G) {
    int low, high, mid, ans;
    low = 0;
    high = 모든 간선의 가중치의 합;
    ans = 0;
    while(low <= high) {
        mid = (low + high) / 2;
        if (TSP_Decision(G, mid)) {
            ans = min(ans, mid);
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return ans;
}

이런식으로 바이너리 서치를 통해 TSP_Decision의  K값을 바꿔가며 log N번 실행하면 최적화 문제의 답을 구할 수 있습니다.

high값을 모든 간선의 가중치의 합으로 초기화한 이유는 그래프에서 나올 수 있는 가장 긴 경로로 지정해주기 위해서입니다.

---

2. 결정 불가능한 문제

컴퓨터는 우리가 생각할 수 있는 거의 모든 계산을 다 할 수 있습니다. 그렇다면 컴퓨터가 계산할 수 없는 것은 무엇일까요? 컴퓨터로 계산할 수 없다고 증명된 문제가 하나 있습니다. 컴퓨터과학의 아버지인 앨런 튜링이 제시한 ‘Halting problem’ (정지문제)입니다. 정지 문제란 어떠한 알고리즘에 대한 명세 A와, 그 알고리즘에 대한 입력 I의 쌍 (A, I) 를 입력으로 받아서 알고리즘 A가 입력 I에 대해 언젠간 정지하고 결과를 출력할지 아니면 무한히 실행될지를 결정하는 문제입니다. 이러한 문제를 해결하는 일반적인 알고리즘은 만들 수 없다는 것을 튜링이 증명했습니다. 다음과 같이 귀류법으로 증명할 수 있습니다.

H(A, I) = 알고리즘 A가 입력 I에 대해 정지할지, 무한히 실행될지를 리턴하는 알고리즘

이러한 H가 존재한다 가정하면 우리는 다음과 같은 새로운 알고리즘 G를 만들 수 있습니다.

bool G(B) {
    if (H(B, B) == Yes)
        무한루프;
    else
        return Yes;
}

G에 G자신의 명세를 입력으로 넣으면 어떻게 될까요?

내부적으로 H(G, G) 를 호출하겠죠? H(G, G)의 결과에 따라 두가지 경우의 수가 있습니다.

1. H(G, G)가 YES라는 결과를 낼 경우, 이 때에 G는 무한루프를 돌게됩니다. 따라서 G에 G를 입력으로 넣으면 종료한다는 H의 결과는 잘못됐습니다.
2. H(G, G)가 NO라는 결과를 낼 경우, 이 때에 G는 종료하게 됩니다. 따라서 G에 G를 입력으로 넣으면 무한루프를 돈다는 H의 결과는 잘못됐습니다.

따라서 이러한 H는 존재할 수 없습니다.

정지문제와 같이 유한시간내에 계산할 수 없는 문제들을 undecidable한 문제라고 합니다. 반대로 유한시간내에 계산할 수 있는 문제들을 decidable한 문제라고 합니다. 

---

3. P문제 (Polynomial time problem)

P는 결정문제들 중에 다항시간에 해결할 수 있는 문제들의 집합입니다. 즉 비교적 빠른 시간내에 쉽게 계산할 수 있는 문제들입니다. 가령 'n개의 정수가 입력으로 주어졌을 때, 그 중에 10보다 큰 정수가 존재하는가?’ 라는 문제는 n개의 정수를 모두 10과 비교해보는 방법으로 다항시간에 해결할 수 있으므로 P에 속합니다.

---

4. NP (Nondeterministic Polynomial time problem, 비결정론적 다항시간 문제)

NP는 결정 문제들 중 답이 Yes일 때, 적절한 증거물을 바탕으로 다항시간에 검증가능한 문제들의 집합입니다. 예를 들어 어떠한 그래프에 모든 정점을 한번씩만 지나는 경로가 있는지를 결정하는 해밀턴 경로 문제는 NP에 속합니다. 왜냐하면 만약 어떠한 그래프에 해밀턴 경로가 존재한다면 그 해밀턴 경로를 증거물로 삼아서 그 경로가 실제로 그래프에서 유효한 경로인지를 다항시간에 검사할 수 있기 때문입니다. 그 외에도 P문제들을 포함해서 우리가 알고있는 거의 대부분의 문제들은 NP에 속합니다.

그렇다면 NP에 속하지 않는 문제에는 무엇이 있을까요?

먼저 정지문제와 같은 undecidable한 문제들은 당연히 NP에 속하지 않습니다. 에초에 유한시간내에 동작하는 알고리즘을 만들 수 없기 때문입니다. decidable한 문제들 중에 확실히 NP에 속하지 않는다는 것이 증명된 문제가 있는지는 저도 잘 모르겠습니다. 다만 decidable한 문제들 중 아직 NP에 속하는지 여부가 밝혀지지 않았고, 아마도 NP에 속하지 않을 것으로 예상되는 문제는 존재합니다. ‘어떠한 그래프에 해밀턴 경로가 존재하지 않는가?’라는 문제는 decidable 하지만, 아직 NP에 속하는지 여부는 밝혀지지 않았습니다. 이 문제에 대한 답이 Yes일 때, 즉 어떠한 그래프에 해밀턴 경로가 존재하지 않을 때, 이를 다항시간내에 입증할 증거물과 알고리즘을 발견하지 못했기 때문입니다. 생각해보면 어떠한 그래프에 해밀턴 경로가 없다는 것을 입증하기 위한 증거물로는 이 그래프에 존재하는 모든 경로(이건 경우의 수가 이미 다항식 스케일을 넘어갑니다) 혹은 그래프 자체밖에는 떠오르는 것이 없습니다.

---

5. P-NP 문제

밀레니엄 문제인 P-NP문제는 집합P와 NP가 서로 같은지 다른지를 증명하는 문제입니다. P는 정의상 이미 NP의 부분집합이므로 다르게 말하자면 집합 P가 NP의 진부분집합인지 아닌지를 증명하는 문제입니다. 즉, NP에 속하는 문제들 중 단 하나라도 절대로 다항시간 알고리즘을 찾을 수 없다는 것을 증명하면 P ≠NP가 되는것이고, 모든 NP문제들의 다항시간 알고리즘을 찾거나, 찾을 수 있다는 것을 증명한다면 P = NP가 되는것입니다. 전자는 그렇다 치더라도 후자는 정말 답이 없어 보입니다. 왜냐하면 미래에 나올 어떠한 NP문제에 대해서도 다항시간 알고리즘을 찾을 수 있다는 것을 증명해야 하기 때문인데, 사실 저도 처음엔 말도 안되는 소리로 들렸습니다. 하지만 잠시후에 설명드릴 NP-complete 이라는 집합에 대해 알게되면 그렇게 말도 안되는 소리는 아닐수도 있다는 것을 알 수 있습니다

---

6. 다항시간 환원 (polynomial time reduction)

문제 A, B가 있고 B를 해결하는 알고리즘 N이 있을 때, A의 입력을 다항시간내에 B의 입력 형태로 변환시켜서, 알고리즘 N을 통해 A의 답을 구할 수 있다면 A는 B로 다항시간 환원이 가능하다라고 합니다. 어떤 문제 A가 B로 다항시간 환원 가능하다면 문제 B를 다항시간내에 해결할 수 있을 때, 문제 A도 다항시간내에 해결할 수 있습니다. 따라서 이런 경우 B는 최소한 A보다는 어려운 문제라고 할 수 있습니다.

예를들어

문제 A(boolean[] arr, k) = boolean형 배열 arr에서 원소들 중에 값이 true인 것들이 k개 이상인지를 결정하는 문제

문제 B(int[] arr, k) = 정수형 배열 arr에서 원소들의 값의 합이 k 이상인지를 결정하는 문제 

문제 A는 문제 B로 다항시간 환원이 가능합니다.

문제 A의 입력 배열에서 true → 1, false → 0으로 하는 새로운 정수형 배열을 만들어서 B의 입력으로 사용합니다. 이 변환은 다항시간내에 할 수 있고, 결과 또한 A의 결과와 같습니다. 따라서 A는 B로 다항시간 환원이 가능하고, A는 B보다 쉬운 문제라고 할 수 있습니다.

---

7. NP-complete

NP-complete라는 집합의 정의는 다음과 같습니다

NP-complete = {p 는 NP의 원소 | 다른 모든 NP에 속하는 문제들이 p로 다항시간 환원이 가능}

즉, NP-complete은 다른 모든 NP문제들보다 어려운 NP문제의 집합입니다. 즉, NP-complete에 속하는 문제중 1개라도 다항시간 알고리즘이 발견된다면, 다른 모든 NP문제들의 다항시간 알고리즘도 만들 수 있다는 말이 됩니다. 그렇다면 다른 모든 문제들, 심지어는 미래에 나올 어떠한 NP문제 까지도, 어떠한 문제p로 다항시간 환원이 가능하다는걸 대체 어떻게 증명을 할까요..? 그런 문제가 존재는 할까요? 하지만 놀랍게도 Cook이라는 사람이 SAT문제가 NP-complete이라는 걸 증명해냅니다. 이에 대한 증명은 저도 아직 공부해 본 적이 없습니다만, 어쨌거나 그래서 SAT문제는 최초의 NP-complete문제가 됩니다. 이 증명에 대해 궁금하신 분은 Cook-Levin Theorem을 찾아보시면 됩니다.

SAT문제는 어떠한 논리식이 주어젔을때, 그 논리식의 변수들에 true/false 를 적절히 할당하여, 그 식이 참이 되도록 할 수 있는지를 결정하는 문제입니다. 가령 (a | b) & (b | !c) & !b 와 같은 식은 a = true,  b = false, c = false로 할당을 하면 참이 됩니다. 하지만 (a | b) & !a & !b 와 같은 식은 어떻게 할당을 해도 전체 식을 참으로 만들 수 없습니다. Cook씨는 다른 모든 NP문제들이 이러한 SAT문제로 다항시간 환원 가능하다는 것을 증명했습니다. 따라서 만약 SAT문제에 대한 다항시간 알고리즘을 발견하다면, 다른 모든 NP문제들도 다항시간 알고리즘이 존재한다는 말이 되고, 그렇게되면 P = NP가 됩니다. 또한 Cook씨의 증명 이후에 NP-complete에 다른 많은 문제들이 들어가게 되었습니다. 왜냐하면 어떤 문제가 NP-Complete에 속한다는 것을 증명하는 것이 쉬워졌기 때문입니다. 어떤 문제 p가 NP-complete에 속할 때, p가 다른 NP문제 q로 다항시간 환원이 가능하다면 q도 NP-complete이 됩니다. 왜냐하면 다른 모든 NP문제가 p로 환원이 가능한데 p가 q로 환원이 가능하다면, 다른 모든 문제가 q로 환원 가능한 것이기 때문입니다. 그렇게 Hamiltonian cycle, knapsack, vertex cover 등등의 다양한 문제들이 NP-complete에 속하게 되었습니다. 

---

종합하면 위와 같은 벤다이어그램이 나옵니다. P-NP 문제는 결국 P ∩ NP-complete 이 저 그림처럼 공집합일지, 아니면 P에 속하는 NP-complete 문제가 발견되어서 결국 P = NP가 될지를 증명하는 문제입니다.