컴퓨터 과학의 가장 큰 문제: P 대 NP

클레이 수학연구소가 아주 어렵고 흥미롭다고 보아 밀레니엄 문제로 정한 수학 문제가 일곱 개 있다. 이 가운데 어느 하나를 풀면 상금 100만 달러를 받는다. 그중 하나는 컴퓨터 과학과도 관련이 있는 P 대 NP 문제이다. 이 문제가 무엇에 관한 것인지 알아보자.

솔직히 말하면 쉽게 설명하기는 어렵다. 어쨌든 밀레니엄 문제이니까. 그러니 맛있는 녹차를 한 잔 우려 놓고 🍵 시작해 보자. 먼저 컴퓨터 과학과 알고리즘의 세계에서 네 가지 문제를 살펴본다. 각 문제를 분석하고, 글자 P, NP와 어떤 관계가 있는지 알아본다.

문제 1: 가장 작은 수 찾기

P 대 NP는 알고리즘과 그 복잡도에 관한 문제이다. 눈앞에 종이쪽지 100장을 쏟아 놓았다고 하자. 쪽지마다 수가 하나씩 적혀 있고, 가장 작은 수가 적힌 쪽지를 찾아야 한다. 시간이 얼마나 걸릴까?

30초? 2분?

이론 컴퓨터 과학에서는 이런 시간 단위에 그다지 관심이 없다. 관심 있는 것은 오히려 연산의 횟수이다. 그래서 질문을 조금 바꿀 수 있다. 가장 작은 수를 찾았다고 확신하려면 쪽지를 몇 장 확인해야 할까? 답은 쪽지를 모두 확인해야 한다는 것이다. 가장 작은 수가 마지막 쪽지에 있을 수도 있기 때문이다. 쪽지가 100장이면 100장을 확인해야 한다. 1,000장이면 1,000장을 확인해야 한다. 일반적으로 쪽지가 n장이면 n장을 확인해야 한다.

이것을 알고리즘의 복잡도라고 한다. 쪽지가 n장이고 가장 작은 수를 찾는 데 연산을 n번 해야 한다면, 가장 작은 수를 찾는 이 알고리즘의 복잡도는 n이다. 복잡도가 일차함수로 나타나므로 이를 선형 복잡도라고도 한다.

좋다, 쪽지 100장을 모두 살펴보고 가장 작은 수가 17이라고 답했다고 하자. 이 답이 맞는지 어떻게 확인할 수 있을까? 쪽지를 다시 모두 살펴보고 더 작은 수가 없는지 확인하는 수밖에 없다. 즉 가장 작은 수를 찾는 사람도 쪽지 n장을 보아야 하고, 그 답을 확인하는 사람도 똑같이 해야 한다. 따라서 결과를 검증하는 복잡도도 n, 즉 선형 복잡도이다.

결과를 찾는 것보다 확인하는 것이 더 쉬운 알고리즘도 있을까?

문제 2: 두 수의 곱

크기가 같은 쪽지 더미 두 개를 쏟아 놓았다고 하자. 이번에도 쪽지마다 수가 하나씩 적혀 있다. 더미 A에서 수 하나, 더미 B에서 수 하나를 골라 두 수의 곱이 918이 되게 해야 한다. 예를 들어 두 더미가 다음과 같다고 하자.

$\begin{array}{rcl} A & = & {49, 11, 32, 54, 15} \\ B & = & {17, 64, 74, 61, 21} \end{array}$

곱이 918이 되는 두 수를 어떻게 찾을 수 있을까? 가능한 경우를 모두 해 보면 된다. 경우는 몇 가지일까? 꽤 많아서 25가지이다. 먼저 더미 A의 첫 번째 수 49에 더미 B의 수를 하나씩 곱해 보자.

$\begin{array}{rcl} 49 \cdot 17 & = & 833 \\ 49 \cdot 64 & = & 3136 \\ 49 \cdot 74 & = & 3626 \\ 49 \cdot 61 & = & 2989 \\ 49 \cdot 21 & = & 1029 \end{array}$

918이 되는 쌍은 없다. 따라서 더미 A의 나머지 수로도 똑같이 해 본다. 11에 대해 다섯 쌍, 32에 대해 다섯 쌍, 54에 대해 다섯 쌍, 마지막으로 15에 대해 다섯 쌍이다. 모두 25쌍을 해 볼 수 있다. 그러면 결국 54 · 17 = 918이라는 것을 알게 된다.

이 알고리즘의 복잡도는 얼마일까? 곱한 쌍의 개수를 살펴보자. 두 더미에는 쪽지가 5장씩 있었고, 첫째 더미의 수 5개를 각각 둘째 더미의 수 5개와 곱해 보아야 했다. 모두 5 · 5 = 25가지를 해 본 것이다. 쪽지가 10장씩인 더미 두 개였다면 10 · 10 = 100가지를 해 보아야 한다. 일반화하면, 쪽지가 n장씩인 더미 두 개라면 n · n = n²가지를 해 보아야 한다.

이 알고리즘의 복잡도는 n²이라고 한다. 이차함수로 나타나므로 이차 복잡도라고 한다.

그러면 결과를 확인하는 것은 얼마나 복잡할까? 곱이 918인 두 수가 54와 17이라는 답을 들었다면, 답한 사람이 했던 것처럼 두 더미의 모든 쌍을 살펴볼 필요가 없다. 이 한 쌍 54 · 17만 곱해 보면 답이 맞는지 알 수 있다. 즉 이 문제를 푸는 데는 곱셈이 최대 n²번 필요하지만, 검증하는 데는 곱셈 한 번이면 충분하다. 따라서 검증의 복잡도는 상수 1이다.

이 점에서 이 문제는 계산과 검증에 같은 횟수의 단계가 필요했던 앞의 문제와 크게 다르다.

또 이 문제는 앞의 문제보다 훨씬 복잡하다. 쪽지 1만 장에서 가장 작은 수를 찾는 일이라면 하루면 끝낼 수 있을 것이다. 그러나 쪽지 1만 장짜리 더미 두 개에서 곱을 찾으라고 하면 1만 곱하기 1만, 즉 1억 번의 곱셈을 확인해야 한다. 1초에 곱셈을 한 번씩 하더라도 약 3년이 걸린다.

문제 3: 부분집합의 합

세 번째 문제를 살펴보자. 이번에는 수가 적힌 쪽지 12장을 쏟아 놓고, 적힌 수의 합이 0이 되는 쪽지를 몇 장이든 골라야 한다. 예를 들어 다음과 같다.

$A = {24, - 69, 1, - 15, - 76, - 60, 16, - 83, 48, - 22, 54, - 47}$

이 수들 가운데 합이 0이 되는 수들을 골라 보자. 예를 들어

$24 + 48 - 69 + 1$

의 합은 4이므로 정답이 아니다. 정답은… 직접 찾아보는 것을 숙제로 남긴다 😉. 합이 0이 되는 수의 묶음은 하나뿐이다. 이 문제가 얼마나 어려운지 직접 느껴 볼 수 있을 것이다.

이제 이 문제의 복잡도를 알아야 한다. 이 계산은 그리 간단하지 않으므로 관심 있는 사람만 읽어도 된다. 이 문제의 복잡도를 어떻게 계산하는지 궁금하다면 계속 읽고, 그렇지 않다면 다음 절로 건너뛰어도 된다. ⏩

합이 0이 되는 수의 묶음은 어떻게 찾을 수 있을까? 수의 가능한 조합을 모두 해 보는 수밖에 없다. 두 수의 묶음, 세 수의 묶음, 네 수, 다섯 수의 묶음을 모두 만들어 보고, 묶음마다 합이 0인지 확인해야 한다. 이런 조합은 몇 개일까?

더 작은 집합으로 살펴보자. 세 수의 집합 B = {5, 7, 9}로 만들 수 있는 서로 다른 수의 묶음, 즉 부분집합은 몇 개일까? 모두 8개이다.

$\begin{array}{rcl} B_{1} & = & {} \\ B_{2} & = & {5} \\ B_{3} & = & {7} \\ B_{4} & = & {9} \\ B_{5} & = & {5, 9} \\ B_{6} & = & {5, 7} \\ B_{7} & = & {7, 9} \\ B_{8} & = & {5, 7, 9} \end{array}$

공집합 B₁도 센 것에 주의하자. 지금은 별로 쓸모가 없지만 빠짐없이 세기 위해 넣었다. 계산을 간단하게 하기 위해 부분집합마다 이진 벡터를 하나씩 대응시킨다. 이진 벡터는 00101010처럼 0과 1을 늘어놓은 것일 뿐이다. 여기서는 길이가 3인 이진 벡터를 쓴다. 벡터는 다음과 같이 대응시킨다. 101은 “원래 집합의 첫째 수와 셋째 수는 들어 있고 둘째 수는 들어 있지 않은” 부분집합, 즉 집합 {5, 9}에 대응시킨다. 벡터 110은 “원래 집합의 첫째 수와 둘째 수는 들어 있고 셋째 수는 들어 있지 않은” 부분집합, 즉 집합 {5, 7}에 대응시킨다. 나머지도 마찬가지이다.

$\begin{array}{rcl} B_{1} = {} & \to & 000 \\ B_{2} = {5} & \to & 100 \\ B_{3} = {7} & \to & 010 \\ B_{4} = {9} & \to & 001 \\ B_{5} = {5, 9} & \to & 101 \\ B_{6} = {5, 7} & \to & 110 \\ B_{7} = {7, 9} & \to & 011 \\ B_{8} = {5, 7, 9} & \to & 111 \end{array}$

부분집합마다 길이가 3인 이진 벡터가 단 하나씩 있다. 또 길이가 3인 이진 벡터마다 부분집합이 단 하나씩 대응한다. 따라서 길이가 n인 서로 다른 이진 벡터의 개수를 구하면, 서로 다른 수 n개로 만들 수 있는 조합의 개수를 얻는다. 그러면 이 개수를 세어 보자.

길이가 1인 이진 벡터는 0과 1의 두 개이다.

길이가 2인 이진 벡터는 길이가 1인 이진 벡터마다 끝에 0을 붙여서 얻는다. 그러면 00과 10을 얻는다. 다시 길이가 1인 벡터마다 끝에 1을 붙이면 01과 11을 얻는다. 이렇게 길이가 2인 벡터 00, 01, 10, 11을 모두 얻었다.

길이가 3인 이진 벡터는 길이가 2인 이진 벡터마다 끝에 0을 붙인 000, 010, 100, 110과 1을 붙인 001, 011, 101, 111이다.

길이가 늘어날 때마다 이렇게 계속한다. 이진 벡터의 길이가 1 늘어나면 서로 다른 이진 벡터의 개수는 2배가 된다는 것을 알 수 있다. 따라서 벡터의 길이가 4이면 서로 다른 조합은 모두 2 · 2 · 2 · 2, 즉 16개이다.

일반적으로 원소가 n개인 집합 M이 있을 때, 집합 M의 모든 부분집합의 개수는 길이가 n인 서로 다른 이진 벡터의 개수와 같고, 그 값은 다음과 같다.

$\underset{n 번}{\underset{⏟}{2 \cdot 2 \cdot \dots \cdot 2}} = 2^{n}$

2ⁿ이든 n²이든 마찬가지 아닐까 🤷‍♂

따라서 수 n개의 집합으로 만들 수 있는 서로 다른 부분집합은 2ⁿ개이다. 이 예에서는 수가 n = 12개이므로 2¹²가지, 즉 4096가지 조합을 확인해야 한다. 이 문제의 복잡도는 2ⁿ이라고 한다. 지수함수로 나타나므로 지수 복잡도라고 한다.

앞의 문제는 복잡도가 n²이었고, 이 문제는 복잡도가 2ⁿ이다. 아주 비슷해 보이지 않는가? 하지만 지수가 상수일 때와 변수 n일 때는 큰 차이가 있다. n = 4이면 다음과 같다.

$\begin{array}{rclrc} n^{2} & = & 4^{2} & = & 16 \\ 2^{n} & = & 2^{4} & = & 16 \end{array}$

좋다, 아직은 값이 같다. n = 10이면 어떨까?

$\begin{array}{rclrc} n^{2} & = & 10^{2} & = & 100 \\ 2^{n} & = & 2^{10} & = & 1024 \end{array}$

이런, 지수함수가 치솟아서 어느새 이차함수의 약 10배가 되었다. n = 20이면 어떨까?

$\begin{array}{rclrc} n^{2} & = & 20^{2} & = & 400 \\ 2^{n} & = & 2^{20} & = & 1 048 576 \end{array}$

n = 20일 때 지수 복잡도는 이차 복잡도의 약 2,600배이다. 이처럼 지수함수는 이차함수보다 훨씬 빨리 커진다. 다음에 또 어떤 감염병이 인구 안에서 지수적으로 퍼질 때 이 사실을 떠올려 보자.

쪽지가 20장이면 1,048,576가지 조합을 확인해야 한다. 꽤 많다.

결과가 맞는지 검증하는 방법

찾은 수의 묶음이 정말로 합이 0인지 검증하는 데는 시간이 얼마나 걸릴까? 꽤 빠르다. 이 묶음 하나의 수를 더해 보기만 하면 된다. 합이 0이면 올바른 쪽지 묶음을 찾은 것이고, 합이 다르면 잘못된 묶음을 찾은 것이다.

이번에도 결과를 확인하는 것이 결과를 찾는 것보다 훨씬 쉽다는 것을 알 수 있다.

문제 4: 외판원 문제

외판원 문제는 가장 유명한 알고리즘 문제 가운데 하나이다. 대략 이런 문제이다. 비를 파는 외판원이 있다. 이 외판원은 먹고살려면 여기저기 많이 다녀야 한다. 그래서 우리나라의 큰 도시 14곳을 모두 방문하기로 했다. 낭비는 싫으니 이 도시들을 모두 지나는 가장 짧은 경로를 찾기로 했다. 그 가장 짧은 경로를 찾는 것이 문제이다.

가장 짧은 경로는 어떻게 찾을 수 있을까? 가능한 경우를 모두 해 본다.

문제를 간단하게 만들 수 있다. 어느 두 도시 사이에도 가장 짧은 길이 하나씩 있다고 하자. 모든 도시를 지나는 가장 짧은 경로는 어떻게 찾을까? 도시는 14곳이다. 따라서 출발할 곳은 14가지이다. 서울에서 출발했다고 하자!!! 서울에서는 어디로 갈 수 있을까? 이론적으로는 다른 어느 도시로든 갈 수 있다. 따라서 남은 13곳 가운데에서 고를 수 있다.

여기까지만 해도 처음 두 도시를 방문하는 방법이 모두 14 · 13가지라는 것을 알 수 있다. 출발할 곳이 14가지이고, 그다음에는 남은 13곳 가운데에서 고르기 때문이다.

두 번째 도시에 도착하면 계속 가야 한다. 이미 두 도시를 들렀으므로 남은 12곳 가운데 한 곳으로 갈 수 있다. 따라서 처음 세 도시를 방문하는 방법은 모두 14 · 13 · 12가지이다.

세 번째 도시를 방문하면 남은 11곳 가운데 한 곳을 고르고, 그다음에는 남은 10곳 가운데 한 곳을 고르는 식으로 계속한다.

모든 도시를 방문하고 나면 고를 수 있었던 경우는 모두

$14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

가지라는 것을 알 수 있다. 느낌표로 나타내는 계승(팩토리얼)이 떠오를 것이다. 이 곱은 14!과 같다고 할 수 있다.

$14! = 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

따라서 14곳의 도시를 모두 지나는 경로는 14!가지이다. 많을까? 꽤 많다. 다음과 같기 때문이다.

$14! = 87 178 291 200.$

일반적으로 도시 n곳 사이의 가장 짧은 경로를 찾으려면 서로 다른 경로를 n!가지 해 보아야 한다. 따라서 이 풀이의 복잡도는 n!이다.

찾은 결과가 맞는지는 어떻게 검증할까? 가장 짧은 경로가 부산에서 서울, 그다음 대구로 가는 식이라는 답을 들었다면, 그 답이 맞는지 어떻게 확인할 수 있을까? 꽤 어렵다 🤷‍♂. 경로를 들여다보아도 그 경로가 가장 짧은지 쉽게 확인할 방법이 없다. 사실상 계산 전체를 다시 해야 한다. 따라서 결과를 검증하는 복잡도도 n!이다.

P 클래스와 NP 클래스

지금까지 네 가지 문제와 그 문제를 푸는 알고리즘을 살펴보고, 해를 찾는 것과 그 해를 확인하는 것이 얼마나 복잡한지 분석했다. 이를 정리하면 다음 표와 같다.

문제	풀이의 복잡도	검증의 복잡도
가장 작은 수	n	n
두 수의 곱	n²	1
부분집합의 합	2ⁿ	n
외판원	n!	n!

이제 이 문제들을 두 무리로 나누어 보자. 첫째 무리는 풀기 쉬운 문제이다. 복잡도 n, n², n³, n⁴ 등으로 풀 수 있는 문제이다. n²과 같은 식을 다항식(polynomial)이라고 하므로 이런 문제의 모임을 글자 P로 나타낸다. 즉 P 클래스는 다항 시간에 풀 수 있는(복잡도가 예를 들어 n²이나 n⁷인) 문제를 모은 것이다. 대체로 비교적 쉽게 풀 수 있는 문제들이다.

따라서 P 클래스에는 풀이의 복잡도가 n인 문제 1(가장 작은 수 찾기)과 풀이의 복잡도가 n²인 문제 2(두 수의 곱)가 속한다. 둘 다 다항식이기 때문이다.

둘째는 NP 클래스이다. NP 클래스는 다항 시간에 검증할 수 있는 문제를 모은 것이다. 따라서 마지막 문제를 뺀 모든 문제가 NP 클래스에 속한다. 외판원 문제는 다항 시간에 검증할 방법을 모른다. 앞의 세 문제는 다항 시간에 검증할 수 있다.

외판원 문제는 다항 시간에 풀지도, 검증하지도 못한다. 따라서 외판원 문제를 위해서는 더 어려운 문제를 모은 또 다른 클래스가 필요하다. 그런 클래스도 있지만 지금은 관심 대상이 아니다.

P 클래스는 NP 클래스의 부분집합이라는 것이 분명하다. 즉 P 클래스에 속하는 문제는 모두 NP 클래스에도 속한다. 이치에 맞는 일이다. 어떤 문제를 다항 시간에 풀 수 있다면 그 결과를 다항 시간에 검증할 수도 있다.

P-NP 문제

그러면 거꾸로도 성립할까? NP 클래스에 속하는 문제는 모두 P 클래스에도 속할까? 즉 어떤 문제의 결과를 다항 시간에 검증하는 방법이 있다면, 그 문제를 다항 시간에 푸는 알고리즘도 있을까?

예를 들어 문제 3(부분집합의 합)의 결과는 다항 시간에 검증할 수 있다. 하지만 이 문제를 풀 때 쓴 알고리즘은 다항 시간 알고리즘이 아니라, 지수 복잡도 2ⁿ을 갖는 알고리즘이었다. 그런데 이 문제를 다항 시간에 푸는 알고리즘이 없다고 확실히 말할 수 있을까?

알 수 없다!

다항 시간에 검증할 수 있는 문제마다 그 문제를 다항 시간에 푸는 알고리즘이 있을 수도 있다. 하지만 아무도 모른다. 그런 알고리즘이 있다는 것을 증명하지도 못했고, 없다는 것을 증명하지도 못했다.

NP 클래스의 문제마다 그 문제를 다항 시간에 푸는 알고리즘이 있다면, NP 클래스는 사실 P 클래스와 같다는 뜻이 된다. P 클래스의 모든 문제가 NP 클래스에 속하고, NP 클래스의 모든 문제가 P 클래스에 속하므로 두 클래스는 같아진다.

따라서 P-NP 문제는 P 클래스와 NP 클래스가 같은지, 아니면 서로 다른 문제의 모임인지를 묻는 문제이다.

즉 P = NP이거나 P ≠ NP이다. 어느 쪽인지는 아무도 모른다. 이것을 밝혀내면 상금 100만 달러와 영원한 명성, 그리고 아마 컴퓨터 과학의 노벨상이라 할 수 있는 튜링상도 받게 될 것이다.

P = NP이면 어떻게 될까

P = NP라면 무슨 일이 일어날까? 무슨 일이 일어날지 말하기는 그리 간단하지 않다. NP 클래스의 모든 문제에 대해 그 문제를 다항 시간에 푸는 알고리즘이 있다는 것을 알게 될 것이다. 예를 들어 문제 3(부분집합의 합)을 다항 시간에 푸는 알고리즘이 있다는 것을 알게 된다. 하지만 여기에는 세 가지 함정이 있다.

그런 알고리즘이 있다는 것을 안다고 해서 그 알고리즘을 찾을 수 있다는 뜻은 아니다. 다항 시간에 문제를 푸는 알고리즘이 있다는 것은 알지만, 앞으로 100년이 더 지나도 그 알고리즘을 만들지 못할 수도 있다. 일반 상대성 이론이 블랙홀의 존재를 예측했지만, 블랙홀의 첫 “사진”을 찍기까지 수십 년이 더 걸린 것과 비슷하다.
다항 시간 알고리즘이 있다고 해서 그 알고리즘이 빠르다는 뜻도 아니다. 복잡도가 n¹⁰⁰인 알고리즘을 찾을 수도 있다. n¹⁰⁰도 다항식이기 때문이다. 복잡도 2ⁿ과 n¹⁰⁰을 비교해 보면, n이 비교적 작은 동안에는 복잡도가 2ⁿ인 알고리즘 쪽이 연산이 더 적게 필요하다. 예를 들어 n = 20일 때 2²⁰ = 1,048,576이지만, 20¹⁰⁰은 약 130자리의 수로, 1,048,576보다 자릿수가 약 120개나 더 많다. 따라서 이 다항 시간 알고리즘이 현실에서는 지수 시간 알고리즘보다 느리다. 적어도 n이 비교적 작은 동안은 그렇다.
그래도 빠른 다항 시간 알고리즘을 찾아낸다면 많은 문제를 더 빠르고 정확하게 풀 수 있을 것이다. 물론 좋은 소식이지만 나쁜 면도 있다. 어떤 문제는 풀기 어렵다는 사실에 기대는 분야가 있는데, 바로 암호학이다. 따라서 지금 쓰는 암호를 훨씬 쉽게 깨뜨릴 수 있게 될지도 모른다.

막간: 여기까지 읽은 보상으로 문제 3의 답을 알려 주겠다. 답은 24 + 1 − 60 + 16 − 83 + 48 + 54이다.

P ≠ NP이면 어떻게 될까

P 클래스와 NP 클래스가 서로 다르다면 그다지 큰일은 일어나지 않는다. 대체로 지금 상태 그대로이기 때문이다. 현재로서는 NP의 어려운 문제를 다항 시간에 푸는 알고리즘이 없고, 누군가 P ≠ NP를 증명한다면 그 상태가 영원히 이어질 뿐이다. P = NP를 증명하는 쪽이 훨씬 큰 사건일 것이다.

대중문화 속의 P-NP 문제

“심슨 가족”의 어느 에피소드에서는 호머가 일종의 평행 세계에 들어가는데, 그곳에 P = NP라는 식이 보인다. youtube.com에서 볼 수 있다.
한편 “퓨처라마”에서는 창고에 폴더 두 개가 있는데, 하나에는 P, 다른 하나에는 NP라는 이름이 붙어 있다. youtube.com에서 볼 수 있다.
드라마 엘리멘트리 시즌 2의 두 번째 에피소드 “Solve for X”는 P 대 NP 문제를 풀었을지도 모르는 수학자의 살인 사건을 다룬다.

« 이전: 1 + 2 + 5 · 0은 얼마일까: 곱셈의 우선순위

다음: 트라흐텐베르크의 빠른 덧셈법 »