컴퓨터 과학에는 유명한 난제가 있습니다. 바로 P vs NP입니다. 컴퓨터 과학을 공부하다 보면 언젠간 한 번은 반드시 접하게 되는 흥미롭고도 신기한 문제인데요. 이번 포스트에서는 이에 대해서 함께 알아보도록 하겠습니다.
저는 P vs NP 문제를 대학생 시절 알고리즘 수업을 들을 때 처음 접하였습니다. 솔직히 말씀드리면, 당시에는 진짜 하나도 이해를 못했다고 해도 과언이 아니었습니다. P, NP 내용이 기말고사 범위였는데, 시험 볼 때는 교과서나 강의 자료의 내용을 그저 달달 외워서 베껴 적었던 기억이 나네요. 그 후 대학원 준비를 할 때 P와 NP에 대해서 좀더 알게 되었고, 진학 후에야 그것들을 제대로 이해하는 수준에 이르렀습니다. 그만큼 어렵게 배운 개념이었는데요. 막상 제대로 이해를 한 후에는 그렇게 어려운 개념은 아니었구나를 깨닫게 되었습니다.
이 난제를 정확히 이해하기 위해서는 튜링 머신(Turing machine) 등 계산 이론(theory of computation)의 수많은 개념을 알아야 합니다만, 이 글에서는 최대한 쉽게 전달하기 위해서 그것들을 가능한 한 배제하려고 노력하였습니다. 따라서 글 내용에 엄밀하지 못한 부분이 많으니 읽으실 때 유의하시기 바랍니다. 그럼에도 이 글을 통해 P vs NP가 이런 것이구나 정도를 알고 가신다면 다음에 이에 대해 훨씬 자세하고 엄밀하게 적힌 글을 읽으실 때 도움이 되리라 생각합니다.
이 글은 세부적으로 다음과 같은 사항들을 하나씩 살펴봅니다.
- 결정 문제(decision problem)
- 다항 시간 알고리즘(polynomial-time algorithm)
- 비결정론(nondeterminism)
- P vs NP
결정 문제(Decision Problem)
우리는 컴퓨터로 많은 문제를 해결합니다. 당장 백준 온라인 저지에는 풀 수 있는 수많은 문제가 있습니다. 코딩 테스트에서도 우리는 컴퓨터로 문제를 풀어야 합니다. 그 외에도 여러 예시가 있다는 것을 쉽게 알 수 있습니다. 사실 컴퓨터를 활용한다는 것은 결국 컴퓨터로 어떤 문제를 해결한다는 것과 동일한 의미일 겁니다. 그렇다면 여기서 컴퓨터로 푸는 "문제"라는 것은 도대체 무엇일까요?
우선 예를 들어 보겠습니다. 최소 스패닝 트리 문제(minimum spanning tree problem)를 푼다고 해보죠. 그러면 우리에게는 어떤 그래프와 각 간선의 가중치가 주어져야 합니다. 그러한 정보도 없이 무슨 문제를 풀 수 있을까요? 이제 우리가 찾아야 하는 것을 생각해 봅시다. 이 문제에서 우리는 어떤 스패닝 트리를 찾아야 합니다. 이는 그래프의 모든 정점들을 연결하면서(connected) 순환이 없는(acyclic) 간선 부분집합을 의미합니다. 이조차 만족하지 못한다면 이는 가능한 답이 아닙니다. 그러면, 아무 스패닝 트리를 반환하면 될까요? 아니죠. 개중에서도 가중치의 합이 가장 작은 스패닝 트리를 찾아야 합니다. 그것이 곧 일종의 정답인 셈이죠. 참고로 그러한 스패닝 트리는 여러 개 있을 수 있습니다. 우리는 그중 아무거 하나를 찾으면 됩니다.
문제(problem)의 엄밀한 정의도 결국 이와 같습니다. 우리는 문제를 입력(input)의 집합과 답(solution) 집합 사이의 어떤 관계(relation)로 정의할 수 있습니다. 수학 기호로 표기를 하면 좀더 쉽습니다. 어떤 입력의 집합 \( \mathcal{I} \)와 어떤 답의 집합 \( \mathcal{S} \)가 주어졌을 때, 문제 \(P\)는 \[ P \subseteq \mathcal{I} \times \mathcal{S} \]로 정의됩니다. 이를 해석하자면, 임의의 입력 \( I \in \mathcal{I} \)와 임의의 답 \( S \in \mathcal{S} \)에 대해, 만약 \(I\)의 정답이 \(S\)라면 \( (I, S) \in P \)인 것이고, 그렇지 않으면 \( (I, S) \notin P \)인 것이죠. 관계로 정의되었기에 한 입력에 여러 정답이 존재할 수 있다는 것도 표현할 수 있습니다. 예를 들어, 입력 \(I\)에서 서로 다른 \(S_1, S_2\)가 모두 정답이라면 \( (I, S_1) \in P \), \( (I, S_2) \in P \)로 나타낼 수 있습니다.
세상에는 무한히 많은 문제가 있을 것입니다. 그리고 다양한 형태의 일반적인 문제들을 몽땅 고려하는 것은 쉬운 일이 아니죠. 따라서 우리는 다음과 같은 특정한 형식의 문제에 대해서만 고민해 보고자 합니다. 바로, 입력이 참(true)인지 거짓(false)인지만 따지는 것이죠. 다시 말해, \( \mathcal{S} := \{ \mathsf{true}, \mathsf{false} \} \)를 답 집합으로 갖는 문제만 생각하겠다는 뜻입니다. 이러한 형태의 문제를 우리는 결정 문제(decision problem)라고 부릅니다.
어떤 명제가 참이면서 동시에 거짓일 수는 없습니다. 똑같이 어떤 결정 문제의 어떠한 입력에 대해 참이면서 동시에 거짓이 정답인 경우는 어불성설입니다. 따라서 아래에서는 결정 문제에서 모든 입력이 참이나 거짓 둘 중 하나만 정답으로 한다고 가정하겠습니다.
결정 문제는 일반적인 문제에 비해 매우 제한된 문제만 표현할 수 있을 것으로 보이지만, 사실 우리는 임의의 일반적인 문제를 그에 상응하는 결정 문제로 바꿀 수 있습니다. 다시 최소 스패닝 트리 문제를 예시로 들어 보겠습니다. 원래 문제의 질문은
어떤 그래프와 간선 가중치가 주어졌을 때, 스패닝 트리 중에서 가장 가중치가 작은 것을 찾으시오.
였다면, 이에 상응하는 결정 문제는
어떤 그래프와 간선 가중치, 그리고 어떤 수 \(k\)가 주어졌을 때, 가중치의 크기가 \(k\)를 넘지 않는 스패닝 트리가 존재하는가?
와 같이 정의하면 됩니다. 만약 \(k\)가 최소 스패닝 트리의 가중치보다 작다면 아래의 결정 문제는 거짓이 될 것이고 반대로 크거나 같다면 참이 되겠습니다. 따라서 (방법이 자명하지는 않지만) 적절한 \(k\)를 찾는 것으로 우리는 최소 스패닝 트리의 가중치를 알 수 있게 됩니다.
놀랍게도 제가 대학원 알고리즘 수업 시간에서 배운 바에 따르면 결정 문제만으로도 임의의 문제를 표현하는 데는 큰 문제가 없다고 하더군요. 하지만 정확한 증명도 모르거니와 아래의 내용을 이해하는 데에는 결정 문제가 무엇인지 아는 것만으로 충분하므로 이에 대한 설명은 하지 않도록 하겠습니다.
다항 시간 알고리즘(Polynomial-Time Algorithm)
우리는 항상 빠른 시간에 문제를 해결하고자 합니다. 여러분이 유튜브 영상을 보고 있는데 계속 버퍼링이 걸린다면 매우 짜증이 나겠죠? 그것과 같은 이치입니다. 그렇다면 얼마나 빨리 풀어야 문제를 빨리 풀었다고 얘기할 수 있을까요? 물론 상황에 따라 달라지겠지만, 거시적인 관점에서는 어떤 알고리즘이 입력의 다항 시간(polynomial time)에 문제를 해결할 때 이를 효율적인 알고리즘(efficient algorithm)이라고 부릅니다. 그럼 다항 시간에 해결된다는 게 무슨 뜻일까요?
먼저 알고리즘(algorithm)이 무엇인지 알아봅시다. 저는 컴퓨터과학을 잘 모르시는 분들에게 알고리즘을 설명할 때 주로 다음과 같이 알려 줍니다.
알고리즘은 어떤 문제를 해결하는 방법을 컴퓨터가 이해할 수 있는 단계로 풀어서 기술한 것이다.
컴퓨터가 이해할 수 있는 단계는 곧 CPU의 명령어 정도를 의미합니다. 따라서 복잡한 문제를 풀기 위해서는 알고리즘이 여러 단계를 거쳐야 할 수 있습니다. 이때 어떤 입력에 대해 알고리즘이 거친 단계의 수가 곧 알고리즘의 수행 시간에 대응한다고 볼 수 있습니다.
입력의 크기가 커지면 그만큼 수행 시간이 늘어나는 것은 어찌 보면 당연한 일입니다. 이때, 주어진 입력 \(I\)의 크기를 \(|I| = n\)이라고 하였을 때, 만약 알고리즘이 수행한 단계의 수가 \(n^2 + 3 n + 5\)나 \( 2 n^{100} + 3 n^{50} - n\)과 같이 \(n\)에 대한 어떤 다항식을 항상 넘지 않는다면, 우리는 이 알고리즘이 다항 시간에 동작한다고 말합니다. 참고로, \( \log n \)은 \(n\)보다도 느리게 증가하므로 다항 시간의 기준에 포함됩니다만, \( 2^n \)을 포함하는 식은 \(n^{100}\)이든 \(n^{10000}\)이든 어떤 상수의 지수를 가지더라도 \(n\)의 크기가 무진장 커지면 \(2^n\)이 항상 더 커지게 되므로 다항 시간에 포함되지 않습니다. 후자는 특별히 지수 시간(exponential time)이라고 부릅니다.
비결정론(Nondeterminism)
앞에서 다항 시간 알고리즘을 공부했으므로, P vs NP에서 P가 뜻하는 바는 'polynomial time'일 것이라고 유추할 수 있고 실제로도 그러합니다. 그렇다면 NP의 N이 의미하는 바는 무엇일까요? 쉽게 떠오르는 단어는 아무래도 'no'나 'non' 정도일 겁니다. 다시 말해, 다항 시간과 비다항 시간으로 나뉘었다고 생각하는 것이죠. 안타깝지만, 그렇지 않습니다. 정답은 바로 'nondeterministic'입니다. 우리말로는 '비결정론적'으로 번역되더군요. 처음 들어보시는 분들이라면 도대체 이게 무엇을 의미하고 있는지 잘 와 닿지 않으실 겁니다. 과연 이 단어가 내포하고 있는 의미는 무엇일까요? 이에 대해 (조악한 솜씨나마) 직접 그린 예시와 함께 알아보도록 하겠습니다.
한 모험가가 보물을 찾기 위해 길을 나섰습니다. 모험가가 있는 장소는 여러 지점들과 지점 사이를 연결하는 길목으로 이루어져 있습니다. 몇몇 지점에는 휘황찬란한 보물이, 또 몇몇 지점에는 무시무시한 독 늪이 있습니다. 모험가는 한 지점에서 출발하며, 당연히 독 늪을 피해 보물을 찾고 싶어합니다. 모험가가 한 지점에 있을 때 길목으로 연결된 다음 지점에 무엇이 있는지는 확인할 수 없습니다. 즉, 직접 가서 확인해야 합니다. 이때, 길목을 따라 움직일 때는 항상 정확히 1분이 소요된다고 합시다. 과연 모험가는 보물을 찾을 수 있을까요? 또 얼마나 빠른 시간에 찾을 수 있다면 찾을 수 있다고, 못 찾는다면 찾지 못한다고 결정할 수 있을까요?
만약 모험가가 출발하는 지점에서 도달할 수 있는 보물이 있다면, 분명 모험가는 보물을 찾을 수 있을 겁니다. 반대로 그러한 보물이 존재하지 않는다면 모험가는 보물이 없다고 결론을 내릴 수 있죠. 따라서 찾을 수 있는지 없는지를 판단하는 것은 쉽습니다. 하지만 이를 얼마나 빠른 시간에 판단할 수 있을까요? 이는 쉽지 않은 문제입니다.
만약 그림 1과 같이 지점들이 일렬로 있고 모험가가 출발하는 지점은 한쪽 끝, 보물이 반대쪽 끝에 있다고 합시다. 그러면 모험가는 "빠른" 시간에 보물이 존재하는지 판단할 수 있습니다. 그냥 죽 앞으로 가다가 보물이 있으면 있다고 결정하면 되기 때문이죠.
여기서 다음과 같은 의문점이 드실 수 있습니다.
만약 지점의 개수가 엄청 많으면 그만큼 오랜 시간이 걸리는 것 아닌가? 그럼에도 여전히 빠른가?
맞습니다. 이 방법은 만약 (출발점을 제외한) 지점의 개수가 100개라면 100분이 걸릴 것이고, 10,000개라면 10,000분이 걸릴 것입니다. 즉, 지점의 개수가 늘어날수록 판단하기까지의 시간도 덩달아 늘어나게 됩니다.
하지만 곰곰이 생각하시면, 그 시간은 보물이 존재하는지를 판단하기 위해서 반드시 소모해야 하는 시간이라는 사실을 파악하실 수 있을 겁니다. 예를 들어, 지점의 개수가 100개일 때, 99분 동안은 모험가가 아무리 노력해도 보물의 바로 앞 지점까지밖에 가지 못합니다. 그곳에서는 다음 지점에 보물이 있을지 독 늪이 있을지 맞출 수 없습니다. 따라서 최소한 100분은 소모해야 보물이 존재하는지 존재하지 않는지를 판단할 수 있습니다. 출발점에서 끝 지점이 멀어지면 멀어질수록 필요한 시간도 동시에 늘어난다는 것을 쉽게 확인할 수 있습니다. 따라서 지금 모험가가 결정할 때까지 걸리는 시간은 어떠한 경우에서든 반드시 소모해야 하는 시간이므로 "빠른" 방법이라고 말할 수 있습니다.
위 예시는 너무 단순하죠. 이번에는 지점마다 갈림길이 있는 경우를 생각해 봅시다. 이 예시에서는 출발점에서 시작해 매 지점마다 새로운 두 갈래길이 있습니다. 이때, 새로운 갈림길은 기존에 방문한 지점은 거치지 않습니다. 몇 번의 갈래길을 거친 후에는 끝 지점에 도달합니다. 끝 지점에는 (그리고 거기에만) 보물 혹은 독 늪이 있으며, 이들은 모두 모험가가 출발하는 곳에서 동일한 거리만큼 떨어져 있습니다. 이 거리를 "깊이"라고 부르겠습니다. 이는 루트(root)가 출발점이고 모든 리프(leaf)가 보물 혹은 독 늪인 완전 이진 트리(complete binary tree)라고 생각하면 편합니다.
그림 2는 보물이 한 개고 깊이가 2인 예시를 나타내고 있습니다. 이때는 과연 모험가는 얼마나 빠른 시간에 보물에 도달할 수 있다고 판단할 수 있을까요? 출발점에서 보물까지의 거리가 2이므로 최소한 2분의 시간은 써먹어야 한다는 것은 쉽게 알 수 있습니다. 최선의 경우에 갈림길을 항상 잘 선택한다면 2분 만에 구할 수도 있습니다. 하지만 항상 갈림길을 잘 선택한다고 말할 수는 없습니다. 따라서 최악의 경우, 모험가는 다른 지점들을 모두 지나고 나서야 보물을 발견할 겁니다. 그때 걸리는 시간은 모든 길목을 한 번씩 지나는 시간인 6분보다 많을 겁니다.(심지어 돌아가는 시간은 고려하지도 않았습니다.)
최소 2분이 필요한 데 6분 정도에 구할 수 있다는 것에 "애걔?"라고 생각하실지 모르겠습니다. 하지만 깊이가 깊어지면 어떻게 될까요?
그림 3은 깊이가 4인 경우를 예시로 나타내었습니다. 이 경우에 갈림길을 잘 선택하기만 하면 4분이면 구할 수 있지만, 최악의 상황에는 30분 이상이 걸릴 수 있습니다. 그리고, 이를 일반화하면 깊이가 \(k\)인 예시에서는 \(k\)분이면 보물을 찾을 수 있지만, 최악의 경우엔 \(2^k\)분 이상 걸릴 수 있습니다. 예를 들어 \(k = 30\)이면, 30분이면 될 일을 최악의 경우 49,000년(year)이 넘는 시간이 걸린다는 뜻이죠. 그 차이가 이제 좀 감이 오시나요?
이런 상황을 대비해서 모험가는 집안 대대로 전해져 내려오는 비기를 갖고 있습니다. 이는 바로 '분신술'입니다. 뜬금없이 웬 분신술이냐고 생각하실 수 있겠지만, 개인적으로는 분신술이 비결정론을 이해하는 가장 쉬운 방법이라고 생각합니다. 여하튼, 모험가의 분신술은 다음과 같은 좋은 특징이 있습니다.
- 분신을 무한정 만들 수 있으며, 심지어 어떤 분신이 새로운 분신을 만들 수도 있다.
- 모든 분신은 서로 소통한다. 소통은 찰나의 시간이면 충분하다.
정말 대단한 분신술이 아닐 수 없습니다. 부럽군요. 각설하고, 이 분신술을 사용하면 위 예시를 빠른 시간에 해결할 수 있습니다.
- 어떤 분신이 갈림길을 만나면 갈림길의 수만큼 새로운 분신을 만들고 각 분신마다 갈림길을 하나씩 할당한다.
- 만약 한 분신이 보물을 발견했다면, 그 자리에서 모험가가 보물을 찾을 수 있다고 결정한다.
- 반대로, 어떤 분신이 독 늪을 발견했다면, 다른 모든 분신에게 이 사실을 알린 후 그 자리에 멈춘다.
- 모든 분신이 멈춘 상태에서 보물을 찾은 분신이 하나도 없다면 모험가는 보물을 찾을 수 없다고 판단한다.
깊이 2인 예시에서 어떻게 동작하는지 따라가 봅시다. 처음 두 갈래길이 있으므로 분신 1과 분신 2를 만들어 각 길목으로 보냅니다. (그림 4)
분신 1은 또 두 갈래길을 마주하게 되죠. 따라서 분신 1-1과 분신 1-2를 만들어 각 길목으로 보냅니다. 분신 2의 경우도 마찬가지입니다. 이 친구도 두 갈래길을 마주하였으니 분신 2-1과 분신 2-2를 생성한 후 각 길목으로 분신들을 보내줍니다. (그림 5)
그러면 분신 1-2가 보물을 발견합니다. 어떤 분신이든 보물을 발견하면 그 자리에서 바로 모험가가 보물에 도달할 수 있다고 결정할 수 있습니다. 다른 분신들은 독 늪을 발견했지만, 어차피 우리의 목표는 모험가가 보물을 찾을 수 있냐이므로 상관할 바가 아닙니다. (그림 6)
만약 끝 지점에 모두 독 늪만 있다면 어떨까요? 그러면 모든 분신들이 독 늪을 발견했다고 알리고 그 자리에서 멈추게 됩니다. 따라서 모험가가 도달할 수 있는 보물이 없다고 판단하게 됩니다. (그림 7)
이번에는 과연 얼마나 빠른 시간에 모험가가 보물에 도달할 수 있는지를 판단할 수 있을까요? 깊이가 \(k\)일 때, \(k\)분 이후에는 모든 지점에 분신이 하나씩 도착하게 됩니다. 모든 분신은 찰나의 시간 동안 서로의 상태를 파악할 수 있죠. 따라서 정확히 \(k\)분이면 모험가의 보물 도달 여부를 파악할 수 있습니다. 앞에서 \(k\)분의 시간은 꼭 필요하다는 것을 살펴보았으므로 분신술을 활용한 이 방법이 매우 "빠른" 방법임을 알 수 있습니다.
어떤 문제를 해결하는 알고리즘을 고안할 때, 우리는 항상 무언가를 선택해야 하는 상황에 빠집니다. 몇 가지 예시를 들어 보죠. 앞에서 본 최소 스패닝 트리 문제에서 우리는 그래프의 각 간선을 넣을지 말지를 결정해야 합니다. 인터벌 스케줄링(interval scheduling)에서는 각 인터벌을 넣을지 말지를 선택해야 합니다. 어렵다고 알려진 문제들은 어떤가요? 배낭 문제(knapsack problem)에서도 우리는 배낭에 물건을 담을지 말지를 결정해야 합니다. 외판원 문제(traveling salesman problem)는 어떨까요? 여기서도 각 도시를 몇 번째 순서에 방문할지 정해야 합니다. (위 문제들은 제가 따로 포스팅하였으니 궁금하신 분은 해당 포스트를 참조하시기 바랍니다.)
결정론적 알고리즘(deterministic algorithm)은 마치 위 예시에서 분신술이 없는 모험가와 같습니다. 따라서 무언가를 선택해야 하는 상황이 왔을 때, 이 알고리즘은 그중 하나만 고른 후에 다음 단계로 넘어갈 수 있습니다. 이는 마치 모험가가 갈림길 중 하나를 택하여 그 길로 모험을 떠나는 것과 같은 맥락으로 보시면 되겠습니다. 이 알고리즘의 수행 시간은 어렵지 않게 구할 수 있습니다. 어차피 매번 하나의 선택만 할 수 있으니 이 알고리즘이 끝날 때까지 수행한 단계의 수와 동일합니다.
반대로 비결정론적 알고리즘(nondeterministic algorithm)은 분신술을 사용할 수 있는 모험가에 대응합니다. 알고리즘이 무언가를 선택해야 하는 상황이 오면, 분신을 소환하는 것처럼 일종의 평행 세계(parallel universe)를 만들어서 각각을 병렬적으로 처리할 수 있죠. 또, 분신들이 찰나의 순간에 소통하는 것처럼 평행 세계끼리도 곧장 소통할 수 있습니다. 따라서, 어떤 평행 세계에서 입력이 참이라는 사실을 알게 되면 곧장 입력이 참이라고 결정할 수 있고, 반대로 모든 평행 세계에서 입력이 거짓이라고 판단하면 입력이 거짓이라고 결정할 수 있게 됩니다. 이러한 알고리즘의 수행 시간은 얼마나 될까요? 모든 평행 세계가 병렬적으로 동작하므로 어떤 평행 세계에서 걸리는 시간의 최댓값으로 정의하는 것이 자연스럽겠죠.
비결정론적 알고리즘을 또 다른 방식으로 정의할 수도 있습니다. 위 모험가 예시에서 먼저 생각해 보겠습니다. 이번에는 모험가에게 분신술의 능력이 없다고 해봅시다. 대신 매 지점마다 누군가가 어느 길목으로 가라는 힌트를 주었다고 가정해 봅시다.
모험가는 주어진 힌트를 따라 "빠른" 시간에 끝 지점에 도달할 수 있습니다. 또한 힌트를 모두 소진한 후에는 쉽게 보물인지 독 늪인지 판단할 수 있습니다. 만약 어떤 힌트를 따라갔더니 보물이 나왔다면, 우리는 바로 모험가가 보물을 찾을 수 있다고 결정할 수 있습니다. 반대로 모험가가 보물을 찾지 못한다면, 어떤 힌트를 주든지 항상 독 늪에 빠지게 될 겁니다.
같은 맥락으로 우리는 비결정론적 알고리즘을 어떤 힌트를 검증하는 결정론적 알고리즘으로 대체할 수 있습니다. 이 결정론적 알고리즘은 주어지는 힌트를 알맞게 해석하여 결정론적으로 진행하며 종국적으로 입력의 참, 거짓 여부를 판단하게 됩니다. 만약 입력이 참이라면, 결정론적 알고리즘이 참이라고 판단할 수 있는 힌트가 존재해야 하며, 반대로 입력이 거짓이라면, 그러한 힌트가 존재해서는 안 됩니다. 우리는 이러한 특징을 만족하는 결정론적 알고리즘을 힌트를 검증한다는 의미에서 verifier라고 부르고, 주어지는 힌트는 certificate이라고 부릅니다. (번역하자면, 검증자와 증거쯤 되겠습니다. 개인적으로 용어는 번역하려고 노력하지만 이번에는 마뜩한 번역을 찾지 못해 영어인 채로 두겠습니다.)
좀더 직관적으로는 certificate이 비결정론적 알고리즘이 최종적으로 생성하는 수많은 평행 세계 중 특정한 평행 세계 하나로 향하는 방법을 알려 주고 있다고 생각하면 편합니다. 이 정보를 토대로 verifier는 추가적인 평행 세계를 생성하지 않고 (즉, 결정론적으로) 해당 경우에 찾아가고 입력이 참인지 거짓인지를 판단하는 것이죠. 만약 입력이 참이라면 평행 세계 중 하나는 분명 참이라는 사실을 알려 줄 것이고, 따라서 그러한 certificate이 존재하겠죠. 반대로 거짓이라면 모든 평행 세계가 거짓일 것이니 그러한 certificate은 존재하지 않게 되는 겁니다.
P vs NP
드디어 P와 NP가 각각 무엇인지 정의할 수 있습니다. P와 NP는 각각 어떤 문제들의 부분집합입니다. P는 그중에서도 어떤 결정론적 알고리즘으로 다항 시간에 해결할 수 있는 문제들의 집합이며, 반대로 NP는 어떤 비결정론적 알고리즘으로 다항 시간에 해결할 수 있는 문제들의 집합입니다.
앞에서 우리는 비결정론적 알고리즘을 verifier와 certificate으로 표현할 수 있다고 하였습니다. 따라서 NP는 다음의 조건을 만족하는 verifier와 certificate이 존재하는 문제들의 집합으로도 나타낼 수 있습니다.
- 입력 \(I\)에 대해, 모든 certificate의 크기는 \(|I|\)의 어떤 다항식을 넘지 않는다.
- 입력 \(I\)와 어떤 certificate \(h\)에 대해, \(|I|\)와 \(|h|\)의 다항 시간에 주어진 \(h\)를 검증하는 verifier가 존재한다.
이렇게 정의된 이유를 좀더 직관적으로 설명해 보겠습니다. 먼저 첫 번째 항목이 필요한 이유입니다. 앞서 certificate을 일종의 어떤 평행 세계로 향하는 이정표라고 했습니다. 그런데 만약 이 길이가 입력에 비해 너무 길다면, 비결정론적 알고리즘의 입장에서 해당 평행 세계에 대해 참, 거짓을 판단하려면 너무 오랜 시간이 필요할 겁니다. 비결정론적 알고리즘의 수행 시간은 최종적으로 생성한 모든 평행 세계의 수행 시간 중 최댓값이라고 하였습니다. 그런데 NP에 속하려면 비결정론적 알고리즘이 다항 시간에 동작해야 합니다. 그러니 길이가 긴 certificate은 NP의 정의에 들어맞지 않습니다.
두 번째 항목도 비슷한 이유입니다. 결론적으로 어떤 문제가 NP에 속하려면 다항 시간에 동작하는 알고리즘이 존재해야 합니다. 그런데 verifier가 이미 다항 시간을 초과한다면 이는 이미 NP에 속할 수 없게 되는 것이죠.
이제 P vs NP 문제를 소개하겠습니다. 그러기 위해서는 둘 사이의 관계를 공부해야 합니다. 모든 결정론적 알고리즘은 비결정론적 알고리즘이기도 합니다. 왜냐하면 비결정론적 알고리즘은 결정론적 알고리즘이 할 수 있는 모든 것을 할 수 있기 때문이죠. 따라서 어떤 문제를 해결하는 결정론적 알고리즘이 존재한다는 말은 그 문제를 해결하는 비결정론적 알고리즘이 존재한다는 말이기도 합니다. 따라서 우리는
\[ \mathsf{P} \subseteq \mathsf{NP} \]
임을 쉽게 알 수 있습니다.
그러므로 P와 NP는 분명 둘 중 하나의 관계일 겁니다.
\[ \mathsf{P} \subsetneq \mathsf{NP} \text{ or } \mathsf{P} = \mathsf{NP} \]
전자가 의미하는 바는 비결정론적 알고리즘으로 다항 시간에 해결하는 방법이 존재하지만 결정론적 알고리즘으로는 도저히 다항 시간에 해결하는 방법이 존재하지 않는 문제가 하나는 있다는 뜻입니다. 반면 후자는 비결정론적 알고리즘으로 다항 시간에 해결할 수 있는 문제는 분명 다항 시간에 결정론적 알고리즘으로도 해결할 수 있다는 뜻이죠. 둘 중에 무엇이 맞는지 엄밀하게 증명하는 문제가 바로 컴퓨터 과학에서 가장 유명한 난제인 P vs NP입니다.
마치며
이것으로 P vs NP에 대한 설명을 모두 마무리하겠습니다. 이 난제는 우리의 삶과 밀접한 연관이 있습니다. 실생활의 많은 문제들이 NP에 속한다는 것은 확실하지만 P에 속하는지는 전혀 모르기 때문입니다. 앞에서 언급한 배낭 문제나 외판원 문제뿐만 아니라 적절한 위치에 물류 창고를 짓는 문제(facility location problem)나 병렬 컴퓨터에서 최대한 균등하게 작업을 할당하는 문제(load-balancing problem) 등 척 보기에도 산업적으로 중요해 보이는 문제들 모두 각각을 다항 시간에 해결하는 비결정론적 알고리즘이 존재하나 결정론적 알고리즘은 존재하는지를 모릅니다.
과거 많은 학자들이 이를 증명하기 위해서 먼저 NP에 속한 문제들 중에서도 "어려운" 문제들이 무엇인지 알아보았습니다. 이런 문제를 연구한 이유는 이 문제들이 다른 NP의 문제들보다 쉽지 않기 때문에 만약 이 문제를 다항 시간에 결정론적으로 해결할 수 있으면 NP의 다른 모든 문제들도 다항 시간에 결정론적으로 해결된다는 것을 보일 수 있고, 반대로 P와 NP가 다르다면 분명 이 문제를 다항 시간에 해결하지 못한다고 증명할 수 있을 것이기 때문입니다. 이 문제를 우리는 NP-완전(NP-complete)하다고 부릅니다. 다음에는 이에 대해서 알아보도록 하겠습니다.
현재 많은 학자들은 P와 NP가 다르다고 생각합니다. 하지만 그 누구도 이를 엄밀히 증명하지는 못한 상황입니다. (이를 풀었다고 주장하는 사람들도 있다고 하는데 현재로서 모두에게 공인된 증명은 존재하지 않습니다.) 과연 뭇 학자들의 예측대로 P와 NP는 다를까요? 아니면 놀랍게도 P와 NP는 같을까요? 이는 매우 흥미로운 주제임에 틀림없습니다.
글에 오류가 있거나, 궁금하신 점이 있으시면 언제든 댓글로 알려주세요. 고맙습니다. :)
'수학적 도구 > Theory of computation' 카테고리의 다른 글
| NP-완전 이해하기 (NP-Completeness) (19) | 2020.11.21 |
|---|
