P-NP 문제

• 상위 문서: 밀레니엄 문제

밀레니엄 문제
미증명 이론	나비에-스토크스 방정식의 해의 존재와 매끄러움
	리만 가설
	버츠와 스위너톤-다이어 추측
	양-밀스 질량 간극 가설
	호지 추측
	P-NP 문제
증명된 이론	푸앵카레 추측

1 개요

수학계의 최종 보스인 밀레니엄 문제 중 하나.

P 집합과 NP 집합이 같은지 다른지를 증명하는 100만 달러가 걸린 문제인데, 알려진 지 40여년이나 지났는데도 아직 풀리지 않고 있다.
그냥 단순하게 이해하면 어떤 문제든 직관이나 수식같은 특별한 방법없이 단순 노가다로 죄다 해결되는가 하는 내용. 인간과 연산장치의 가치 비교를 할 수 있는 문제이기도 하다.
(조금 더 쉽게 설명하면, P집합은 이미 NP의 부분집합이므로, 모든 NP문제가 P인가를 증명하면 된다. 다시 말해서, "쉽게 검산할수 있는 모든 문제들은 모두 쉽게 풀리는가? 혹은 어렵게 풀리는 문제는 없는가?" 가 주 목표.)

2 알고리즘의 시간복잡도

컴퓨터를 사용하여 특정한 계산 문제를 풀기 위해서는, 바로 그 문제에 해당되는 알고리즘을 컴퓨터에게 알려주어야 한다. 그리고 컴퓨터공학자들의 주된 관심사는 그 알고리즘이 문제를 얼마나 빨리 해결할 수 있느냐는 것이다. 물론, 알고리즘에 넣어주는 입력의 크기가 커질수록 알고리즘의 수행시간은 점점 오래 걸릴 것이다. 예를 들어 100자리 숫자 두 개를 더하는 문제를 푸는 데에 100나노초가 걸렸다면, 10000자리 수 두 개를 더하는 문제를 풀 때에는 거의 10000나노초가 소요될 것이다. 그리고 보다 일반적으로 말해서, [math]n[/math]자리의 두 수를 더하는 데에는 약 [math]n[/math]나노초가 소요될 것이다. 이러한 경우에는 알고리즘의 시간복잡도가 [math]O(n)[/math]이라고 표기하는데, [math]O[/math]라는 표시는 간단히 말해, [math]n[/math] 앞에 곱해질 비례상수에 대해서는 별로 신경쓰지 않겠다는 의미이다. 어떤 문제가 [math]O(n)[/math] 알고리즘을 가진다는 것은 그 문제가 컴퓨터에게 아주 쉬운 문제라는 것을 의미한다.

조금 더 복잡한 문제를 생각해보자. 만약 [math]n[/math]자리의 두 자연수를 곱하려고 한다면 얼마나 많은 계산이 필요할까? 손으로 이를 푼다고 생각해보면, 그 중간 과정에서는 [math]n[/math]개의 행이 필요할 것이고, 각각의 행은 다시 [math]n[/math]개의 숫자로 구성되어 있을 것이다. 따라서 [math]n[/math]자리의 두 자연수를 곱하는 문제를 손으로 푸는 방식으로 푼다면, 이는 거의 [math]n^2[/math]에 비례하는 시간을 요구할 것이다. 따라서 이때는 알고리즘의 시간복잡도가 [math]O(n^2)[/math]이라고 한다. 즉, 100자리수의 곱셈을 하는 것은 10자리수의 곱셉을 하는 것에 비해 10배 어려운 문제가 아니라 실은 100배나 어려운 문제라는 것이다. 따라서 곱셈은 덧셈보다는 비교적 어려운 문제이다. 그렇지만 이 정도로는 그렇게 어려운 문제라고 할 수 없다.

만약 a~z까지의 알파벳으로 랜덤하게 구성된 10자리의 패스워드를, 모든 가능성을 다 대입해봄으로써 뚫고자 한다면 얼마나 많은 시도가 필요할까? 잘 알다시피 [math]26^{10}[/math]번의 시도가 필요할 것이다. 이것도 141조라는 어마어마한 숫자이다. 하지만 현대의 슈퍼 컴퓨터를 사용한다면, 141조번 정도의 대입 작업은 실제로 가능한 일의 범위 내에 있다.특수문자가 출동한다면 어떨까 대소문자 구분도 있다 숫자도 포함해보자그러면 100자리의 패스워드를, 모든 가능성을 다 대입하여 풀려면 얼마나 많은 시도가 필요할까? [math]26^{100}[/math]은 10의 100승으로 잘 알려진 구골보다도 몇 경배나 큰 수이다. 즉, 100자리수의 패스워드를 뚫는 것은 10자리수의 패스워드를 뚫는 것과는 비교할 수도 없을 정도로 어려운 문제가 된다. 아마 우주의 모든 원자 각각이 10자리 수의 패스워드의 경우의 수 만큼을 모두 대입해볼 수 있는 능력이 있다고 해도, 온 우주가 힘을 합쳐도 100자리 수의 패스워드를 대입해서 푸는 것은 불가능할 것이다. 우주가 나서서 도와줘도 소용없다! 이것은 [math]n[/math]자리 수의 곱셈의 경우와는 확실히 다른, 어마어마하게 어려운 문제임을 쉽게 짐작할 수 있다. 이때의 시간복잡도는 [math]O(26^n)[/math]이 될 것이다.

앞의 쉬운 문제 두 개와 뒤의 어려운 문제의 차이점은 간단하다. 앞의 문제들에 대한 알고리즘은 [math]O[/math]의 괄호 안에 들어있는 식이 [math]n[/math]에 대한 다항식이었고, 뒤의 어마어마하게 어려운 문제는 [math]O[/math]의 괄호 안에 [math]n[/math]에 대한 지수함수가 들어있다는 것이 중요한 차이점이다. 다항식도 [math]n[/math]이 커지면 값이 빠르게 증가하는 것 같지만, 지수함수의 증가속도에 비하면 그것은 새발의 피에 불과하다. 그래서 우리는 어떤 문제가 쉬운지 어려운지를 간단하게 구분할 수 있다. 다항식 시간 알고리즘이 존재하는 문제는 쉬운(tractable) 문제이고, 다항식 시간 알고리즘이 존재하지 않는 문제는 온 우주가 힘을 모아도 풀기 어려운(intractable) 문제이다. 만약 당신이 어떤 알고리즘을 개발하였다고 해도, 그 알고리즘이 다항식 시간에 작동하지 않는, 너무나도 비효율적인 알고리즘이라면, 그 알고리즘은 어떠한 공학적 흥미도 끌 수 없을 것이다.

다행히도 수학/과학적으로 중요한 많은 문제들이 다항식 시간 알고리즘을 가지는 것으로 확인되었다. [math]n[/math]개의 숫자를 입력받고, 그들을 크기순으로 정렬하는 정렬 문제가 대표적이다. 그 외에도 어떤 도로망의 지도가 주어졌을 때, 주어진 출발지와 목적지 사이의 최단 경로를 찾아내는 문제도 다항식 시간에 풀 수 있다. 그러나 어떤 [math]n[/math]자리 자연수를 소인수분해하는 다항식 시간 알고리즘은 아직까지 아무도 찾아내지 못하였다.

서로 다른 두 문제의 난이도를 비교하는 데에는 환원(reduction)이라고 불리는 기법이 자주 사용된다. 예를 들어, 다음의 두 가지의 문제가 주어졌다고 생각하자.

문제 A: 주어진 [math]n[/math]개의 숫자를 크기 순서로 정렬하는 문제

문제 B: 주어진 [math]n[/math]개 숫자의 중간값을 계산하는 문제

어떤 사람이 문제 A를 쉽게 풀 수 있다면, 그 사람은 문제 B도 쉽게 풀 수 있는 것이 당연하다. 왜냐하면 주어진 숫자들을 정렬하고 나면, 그 중 정 가운데에 있는 수를 뽑기만 하면 그것이 중간값이 될 것이기 때문이다. 이와 같은 일이 벌어진다면, 문제 B를 문제 A로 환원시킬 수 있다고 표현하며, 문제 B의 난이도는 문제 A의 난이도보다 쉽다는 것을 알 수 있다.

3 P 문제와 NP 문제

답이 YES 아니면 NO로 반환되는 문제를 결정 문제라고 한다. 예를 들어, 'a는 b의 배수인가?'와 같은 질문은 결정 문제이다. P와 NP 모두 결정 문제의 분류에 해당한다.

P 문제는 결정 문제들 중에서 쉽게 풀리는 것을 모아 놓은 집합이다. 어떤 결정 문제가 주어졌을 때, 다항식(Polynomial) 시간 이내에 그 문제의 답을 YES와 NO 중의 하나로 계산해낼 수 있는 알고리즘이 존재한다면, 그 문제는 P 문제에 해당된다. [math]n[/math]자리 이하의 수 a와 b가 주어졌을 때, a가 b의 배수인지를 판정하는 것은 유클리드 호제법을 사용하면 [math]n[/math]에 대한 다항식 시간에 계산할 수 있으므로, 'a는 b의 배수인가?'하는 문제는 P 문제에 해당된다.

NP 문제는 결정 문제들 중에서 적어도 검산은 쉽게 할 수 있는 것을 모아 놓은 집합이다. 정확히 말하면, 어떤 결정 문제의 답이 YES일 때, 그 문제의 답이 YES라는 것을 입증하는 힌트가 주어지면, 그 힌트를 사용해서 그 문제의 답이 정말로 YES라는 것을 다항식 시간 이내에 확인할 수 있는 문제가 바로 NP 문제에 해당된다. 예를 들어, [math]\{-5,6,1,2,-10,-7,13\}[/math]과 같이 정수 [math]n[/math]개로 이루어진 집합이 주어졌다고 할 때, '이 집합의 부분집합들 중에서 원소의 합이 0이 되는 집합이 존재하는가?'라는 문제는 아직까지 다항식 시간 알고리즘이 알려져 있지 않다. 곰곰히 생각해보아도, 그냥 모든 부분집합을 다 테스트해보지 않는 이상 답이 YES인지 NO인지 답하기가 어렵다는 것을 알 수 있다. 그렇지만 누군가가 우리에게 [math]\{6,1,-7\}[/math]이라는 힌트를 제공하였다면, 우리는 먼저 이 집합이 원래 집합의 부분집합이라는 사실을 확인하고, 이 집합의 원소의 합이 0이라는 사실을 확인함으로서, 원래 문제의 답이 YES라는 것을 어렵지 않게 확인할 수 있다. 따라서 '크기가 [math]n[/math]인 어떤 정수 집합이 주어졌을 때, 이 집합의 부분집합들 중에서 원소의 합이 0이 되는 집합이 존재하는가?'라는 문제는 적어도 NP 문제인 것은 확실하지만, 이것이 P 문제인지 아닌지는 아직 모르는 상황이라고 할 수 있다.

만약 어떤 P 문제가 주어졌고, 그 문제의 답이 YES라면, 우리는 그 문제의 답에 관한 힌트를 받더라도 그냥 무시하고, 곧바로 그 문제의 답이 YES라는 것을 쉽게 확인할 수 있을 것이므로, 모든 P 문제는 저절로 NP 문제도 된다. 즉, P⊂NP임을 알 수 있다. 하지만 그 역방향인 NP⊂P에 대해서는 참인지 거짓인지 아직 알려져 있지 않다. 만약 모든 NP 문제가 P 문제인 경우, 즉 모든 NP 문제가 다항 시간에 풀 수 있는 알고리즘이 존재함을 증명할 경우 P=NP라는 결론이 된다. 그래서 P=NP인지, 아니면 P≠NP인지를 묻는 것이 바로 P-NP 문제이다. 7대 난제 중에서는 문제의 내용을 이해하기 가장 쉽다.

사실 많은 컴퓨터공학자들은 절대로 P=NP일리가 없다고 믿고 있다. 왜냐하면, P=NP가 의미하는 바는, 만약 어떤 문제가 주어졌을 때, 내가 남이 푼 정답을 검산하는 것만 잘 할 수 있어도, 그것이 곧 내가 혼자서도 그 문제의 정답을 구할 수 있는 능력이 있는 것과 동등하다는, 너무나도 강력한 주장이기 때문이다. 이는 우리가 지금까지 열심히 수학을 공부하면서 몸에 체득해온 직관과는 배치되는 일이다. 방정식의 해를 처음부터 자기가 직접 구해내는 것은 어렵지만, 남이 미리 풀어서 구한 답을 방정식에 대입해서 그게 맞는지 확인하는 일은 훨씬 쉬운 경우가 많다. 따라서 P≠NP라는 것을 쉽게 입증할 수 있을 것 같지만, 불행히도 아직까지는 아무도 올바른 증명을 찾아내지 못하였고, 이것을 증명하는 것이 왜 어려운 일인지를 암시하는 간접적인 결과만이 조금 밝혀져 있을 뿐이다.

4 이해

[math]\text{NP}[/math] 문제에 대해 쉽게 이해하기 위해서 예를 들어보자. 어떤 그래프가 주어졌을 때, "그 그래프의 모든 점을 정확하게 한 번씩만 지나는 경로가 존재하는가?" 이를 '해밀턴 경로 문제'라고 하는데, 만약 그 답이 Yes이고 모범답안으로서 그 그래프상의 모든 점을 정확하게 한 번씩만 지나는 경로가 주어진다면, '그런 경로가 존재한다'는 것을 확인할 수 있을 것이다. 즉 적절한 모범답안이 주어진 경우 Yes라는 대답은 확인할 수 있다. 따라서 '해밀턴 경로 문제 [math]= \text{NP}[/math] 문제'이다. 그러나 그 답이 No라면, 설사 '그런 조건을 만족하지 않는 경로'가 주어진다고 하더라도 '그런 경로가 존재하지 않는다'는 것을 확인할 수는 없을 것이다. 다시 말해서 No라는 답을 다항식 시간 내에 확인할 수 있게 해 주는 종류의 모범답안은 알려져 있지 않다. 따라서 '해밀턴 경로 문제 [math]= \text{co-NP}[/math] 문제'가 아니다. 보다 정확하게는, '[math]\text{co-NP}[/math] 문제'라고 증명되지 않았다. 반대로 어떤 그래프가 주어졌을 때, "그 그래프의 모든 점을 정확하게 한 번만 지나는 경로는 없는가?"라는 문제라면 이는 [math]\text{co-NP}[/math] 문제일 것이다.

• 참고로 '바둑 같은 게임에서 필승법이 존재하는가?'는 [math]\text{NP}[/math] 문제도 [math]\text{co-NP}[/math] 문제도 아니다. 예컨대 바둑에서 '흑이 이기는 어떤 수순'이 주어진다고 하더라도 다른 모든 수순들을 검토해서 서로 비교하지 않는 한 그것이 '흑'에게 필승법이 존재한다는 의미인지 검증할 방법이 없다. 즉 '필승법이 존재하는가?'라는 질문에 대해서는 어떤 기보가 주어지더라도 Yes라는 대답도 No라는 대답도 다항식 시간 내에 확인할 수 없는 것이다.
• 이와 같은 문제에서 '다항식 시간 내에' 해결 가능하다는 것은 다음과 같은 뜻이다. : 바둑판에는 19x19개의 격자가 있는데, 이 격자의 수가 [math]x[/math]개가 있을 때, 문제 풀이에 걸리는 시간의 최대치가 [math]x[/math]에 대한 다항식으로 주어진다는 뜻이다. 바둑판 문제의 경우에는 대략 [math]x![/math]개의 경우를 확인하게 되므로, P 문제가 아니다. 이 문제는 'EXP 완전 문제'임이 증명되어 있다. 즉 이 문제를 [math]T[/math]의 시간 내에 풀 수 있으면 모든 지수함수적(exponential) 시간이 걸리는 문제를 '[math]T[/math] + 다항식' 시간 내에 풀 수 있다.

종종 [math]\text{NP}[/math] 문제에 대해서 "[math]\text{P}[/math] 문제가 아닌 것"으로 설명하는 경향이 있지만, [math]\text{P}[/math] 문제는 다항식 시간 동안 '답을 찾을 수 있는' 문제이고 [math]\text{NP}[/math] 문제는 다항식 시간 동안 '주어진 답이 맞는지 확인할 수 있는' 문제이므로 이 둘은 상호배타적인 관계가 아니다. 다항식 시간 내에 직접 답을 구할 수 있다면 당연히 주어진 답이 맞는지 역시 확인할 수 있으므로, '모든 [math]\text{P}[/math] 문제는 [math]\text{NP}[/math] 문제이며 그와 동시에 [math]\text{co-NP}[/math] 문제'이기도 하다.

사실 더 쉽게 설명할 수 있다. Big-O 표시 기준으로 비결정론적 튜링머신으로 [math]O\left(n^p\right)[/math]만큼 시간이 걸리는 문제를 결정론적 튜링머신으로 풀면 [math]O\left(n^{\left(p+q\right)}\right)[/math]만큼의 시간이 걸리는지, 또한 '모든 [math]\text{NP}[/math] 문제를 이런 식으로 환원할 수 있는지를 확인'하는 것이다. 참고로 [math]\text{P}[/math] 문제는 이미 [math]O\left(n^p\right)[/math]이기 때문에 [math]\text{NP}[/math]문제로 풀면 아무리 못 해도 [math]O\left(n^p\right)[/math]는 나온다. 이렇게 환원되는 알고리즘(그리고 문제)을 찾기 위해 지금도 많은 수학자들이 고심하고 있지만 대부분은 명확한 답을 내놓지 못하고 있다.

더 쉽게 설명하자면, 앞서 언급했듯 '검산'은 하나의 경우에 대해서 옳은지 그른지 보는 것이고, '해결'은 해답이 되는 경우를 찾을 때 까지 모든 경우에 대해 옳고 그름을 따지는 것이다. 따라서 이 문제의 초점을 '문제에서 조합 가능한 경우의 수'로 맞춰서 보면, 문제를 푸는 시간은 최악으로 어림잡아 (중복되지 않는 모든 경우의 개수) × (경우 하나를 검증하는 데 걸리는 최악의 시간)으로 볼 수 있다. 여기서 '중복'이라 하는 것은 부분적인 중복도 포함하는 것이으로, 결국 P-NP 문제의 가장 중요한 쟁점은 이 수학적 귀납법으로 경우의 수를 P의 영역으로 넣을 수 있는지의 여부를 묻는 것으로 볼 수 있다. 대표적인 예로, 정렬 문제의 경우 경우의 수가 [math]n![/math]이지만, 이미 수학적 귀납법으로 [math]O\left(n^2\right)[/math], 나아가 [math]O\left(n \text{log} n\right)[/math]으로 수렴된 바 있다.

앞서 언급한 수학적 귀납법으로 설명할 경우 n의 문제를 푸는 데 T 시간 만큼 걸렸다 가정하면, n+1의 문제를 푸는 데 아무리 못해도 [math]T + O\left(n^k\right)[/math]의 시간 만큼은 나와야 P 문제라 말할 수 있다. 반대로 [math]kT + O\left(n^k\right)[/math]의 시간이 걸렸거나 [math]T + O\left(2^n\right)[/math]의 시간만큼이 걸렸다면 최종적으로는 [math]O\left(2^n\right)[/math] 만큼이 걸리는 것이므로, 이 문제는 P 문제라 말할 수 없으며, 오히려 EXP (완전) 문제라 보는 것이 타당하다. 거기에 수학적 귀납법은 그 특성상 이전까지의 답이 그 다음 요소를 포함한 해답을 보증해야 한다는 전제를 깔기 때문에, 이것을 보장할 수 없는 경우 결국 처음부터 다시 풀어야 한다. 실제로 대부분의 NP 문제는 수학적 귀납법을 적용할 수 없기 때문에 규모가 하나만 늘어나도 시간은 기하급수적으로 증가하게 된다. (이 때문에 P≠NP에 대한 믿음이 굳건해지고 있는 것이다.)

초한기수의 개념을 빌리자면, [math]\aleph_0[/math]개의 답을 동시에 검사할 수 있는 비결정론적 튜링머신에서 [math]\aleph_0[/math]규모의 시간복잡도가 나왔는데, 결정론적 튜링머신에 돌릴 때 [math]\aleph_0[/math]규모의 시간복잡도가 나오면 '[math]\text{P} = \text{NP}[/math]'라 말할 수 있으며, 그렇지 않은 경우는 '[math]\text{P} \neq \text{NP}[/math]'라 말할 수 있는 것이다. 하하, 알레프 판이네 자세한 개념은 해당 문서 참조하자. 실제로 이런 식으로 접근하는 사람도 있긴 한데, 이 경우 증명 불가능함이 증명된 연속체 가설과도 직결되므로, 결국 수학 공리 자체의 한계에 부딪힐 수 밖에 없다. 여기에 초한기수 개념을 도입한다는 것 자체가 알고리즘의 '유한성'을 침해하는 행위라서 주류 수학계에서 받아들이지 않고 있다. 100만 달러 주기 싫었나보다.

5 NP-난해 문제

모든 [math]\text{NP}[/math] 문제를 다항식 시간 내에 어떤 문제로 환원(reduction 또는 transformation)할 수 있는 경우, 그 문제는 '[math]\text{NP}[/math]-난해([math]\text{NP}[/math]-hard) 문제'라고 부른다. 즉 [math]\text{NP}[/math]-난해 문제를 다항식 시간 내에 풀 수 있으면 모든 [math]\text{NP}[/math] 문제를 다항식 시간 내에 풀 수 있다. 물론 [math]\text{NP}[/math]-난해 문제 중에는 [math]\text{NP}[/math] 문제가 아닌 것도 있다. (즉 [math]\text{NP}[/math]보다 풀기 어려운 문제도 [math]\text{NP}[/math]-난해 문제일 수도 있다.) 2016년 MIT 연구진이 슈퍼마리오 브라더스가 [math]\text{NP}[/math]-난해 문제 임을 증명해냈다. 그러니까 그거 못해도 괜찮은거다

6 NP-완전 문제

[math]\text{NP}[/math] 문제들 중에서 [math]\text{NP}[/math]-난해 문제인 것을 가리켜 '[math]\text{NP}[/math]-완전([math]\text{NP}[/math]-complete) 문제'라고 부른다. [math]\text{NP}[/math]-완전 문제를 풀 수 있으면 모든 [math]\text{NP}[/math] 문제를 풀 수 있게 되는 셈이므로 [math]\text{NP}[/math] 문제들 중에서는 가장 어려운 종류의 문제들인 셈이다. 위에서 예로 든 해밀턴 경로 문제도 대표적인 [math]\text{NP}[/math]-완전 문제들 중 하나이다.

만약 [math]\text{NP}[/math]-완전 문제가 [math]\text{P}[/math] 문제라면 '모든 [math]\text{NP}[/math] 문제가 [math]\text{P}[/math] 문제'라는 것이 증명되는 셈이다. 바로 이것이 포인트이다. "모든 [math]\text{NP}[/math] 문제가 사실은 [math]\text{P}[/math]인데 우리가 변환법을 찾지 못하는 것인가?"라는 명제, 즉 '[math]\text{NP}=\text{P}[/math]'가 옳으냐 그르냐에 대한 답을 찾는 것. 만약 [math]\text{NP}=\text{P}[/math]라고 증명되면 그 동안의 알고리즘에 대한 연구가 완전히 바뀌는 대격변이 일어나므로 이 증명은 수학계 뿐만이 아닌 여러 학술계열의 주목을 받고 있다.

참고로 '어떤 문제를 다항식 시간 내에 해결할 수 있는가 아닌가'는 '그 문제를 해결하는데 평균적으로 얼마나 시간이 걸리는가?'가 아니라 '최악의 경우(worst case)에 시간이 얼마나 걸리는가?'를 기준으로 한다. 즉 '다항식 시간 내에 해결할 수 없는 경우'가 하나라도 있으면 그것은 [math]\text{P}[/math] 문제가 아니며, [math]\text{P}[/math] 문제가 아니라고 생각되는 [math]\text{NP}[/math] 문제라고 하더라도 평균적으로는 다항식 시간 내에 해결할 수도 있다.

7 유명한 문제

• 유명한 [math]\text{NP}[/math] 문제 중 하나인 '거대한 자연수의 약수를 찾는 문제'의 경우를 보자. 그 자연수가 거대한 두 소수의 곱인 경우는 소인수분해를 할 방법이 알려져 있지 않다. 그러나 만약 자연수를 무작위로 뽑는 경우라면 높은 확률로 그 자연수의 약수를 적어도 하나는 찾을 수 있다. 우선 '2로 나누어질 확률'부터가 1/2이며, '2, 3, 5, 7 중 적어도 하나로 나누어질 확률'은 3/4이 넘기 때문이다. 즉 대부분의 경우에는 약수를 찾을 수 있지만 그 자연수가 거대한 두 소수의 곱인 경우에는 약수를 찾을 수 없기 때문에, (즉 약수를 찾을 수 없는 경우가 '존재'하기 때문에) 이 문제는 (현재로서는) [math]\text{P}[/math] 문제가 아닌 것이다.

• 여행하는 세일즈맨 문제(Travelling Salesman Problem, TSP)의 경우 '[math]\text{NP}[/math]-완전 문제'이지만, '무작위 알고리즘'을 이용하면 많은 경우에 비교적 높은 확률로 최적의 해답이나 그에 가까운 것을 찾을 수 있다. 그러나 무작위 알고리즘으로는 모든 경우에 항상 최적의 해답을 찾을 수 있는 것은 아니기 때문에 이 문제는 [math]\text{P}[/math] 문제가 아니다.

흔히 알려진 "[math]\text{NP}[/math] 문제 = [math]\text{P}[/math] 문제 + [math]\text{NP}[/math]-완전 문제"라는 공식은 옳지 않다. [math]\text{P}[/math] 문제라고도 [math]\text{NP}[/math]-완전 문제라고도 증명되지 않은 [math]\text{NP}[/math] 문제들도 있기 때문이다. 대표적인 것이 '거대한 자연수의 소인수분해 문제'와 '이산 로그 문제'이다. 물론 이런 문제들이 [math]\text{NP}[/math]-완전 문제가 아니라는 것도 증명되지 않았다. 이는 당연한 일인데, 모든 [math]\text{NP}[/math] 문제가 [math]\text{P}[/math] 문제라면 이는 모든 [math]\text{P}[/math] 문제가 [math]\text{NP}[/math]-완전 문제라는 뜻도 되기 때문이다. 즉 만약 어떤 [math]\text{NP}[/math] 문제가 [math]\text{NP}[/math]-완전 문제가 아니라는 것이 증명되면, 그것은 '[math]\text{P}=\text{NP}[/math]가 틀렸다'는 것에 대한 증명도 된다.

다만 [math]\text{P} \neq \text{NP}[/math]라고 가정하는 경우 [math]\text{NP}[/math]-완전 문제가 아닌 [math]\text{NP}[/math] 문제가 존재한다는 것은 증명되어 있다. 그러나 이것도 특수하게 만들어진 문제를 이용한 존재 증명만이 되어 있을 뿐, [math]\text{P}=\text{NP}[/math]가 아니라는 가정하에서도 실제로 의미가 있는 [math]\text{NP}[/math]문제 중에서 어떠한 것도 [math]\text{NP}[/math]-완전 문제가 아니라고 증명하지는 못하고 있다.

8 수학자들의 생각

대부분의 학자들은 [math]\text{P} \neq \text{NP}[/math]일것이라고 믿는다. 이유는 간단한데, 수많은 학자들이 여러 [math]\text{NP}[/math] 문제들에 대해서 '다항식 시간 내에 풀 수 있는 알고리즘'을 찾으려고 노력해 왔지만 전혀 성과가 없었기 때문이다. 또다른 이유로는, 임의의 명제를 증명하는 문제는 [math]\text{NP}[/math]이고, 검증하는 문제는 [math]\text{P}[/math]인데, 증명은 검증보다 본질적으로 어려운 문제일 것이므로 [math]\text{NP}[/math]와 [math]\text{P}[/math]가 같을 수 없다는 믿음이 있다.

물론 믿음과 증명은 별개이므로, [math]\text{P}=\text{NP}[/math]가 맞다고 믿고 있는 수학자들도 존재한다.

위키백과에 있는 출처에 따르면, 2012년에 이론전산학자 150명을 대상으로 한 설문조사에서는 다를 것이라고 답하는 비율이 81퍼센트나 달했다고 한다.설문조사 결과

9 돈

이 문제는 100만 달러가 걸린 밀레니엄 문제 중 하나이다. 100만 달러를 원하는가? 이 문제를 풀면 된다. 돈 뿐만 아니라 세계적인 명성도 얻을 수 있다. 덤으로 핵전쟁이라도 나서 인류가 다시 동굴에서 살다 돌도끼 들고 사냥하러 뛰어다니기 전까지는 당신의 이름이 대학교 전공 교과서에 실리게 될 수 있다. 물론 '[math]\text{P}=\text{NP}[/math]가 틀렸다'는 것을 증명했을 경우고, 만약 '[math]\text{P}=\text{NP}[/math]가 맞다'는 것을 증명이라도 하는 날이면 대학교 교과서가 아니라 꼬꼬마들 보는 위인전에 당신의 이름이 실리게 된다. [math]\text{P}=\text{NP}[/math]라면 암호계에 대격변이 일어나는 것은 물론, 인공지능이 인간과 완전히 동등하다는 말로 받아들이는 등 많은 인문학계에도 대격변이 일 수 있다. 말하자면 제 2의 아인슈타인이 될 수도 있다. 어느 쪽이든 이 문제를 풀었을 때 받게 될 명성에 비하면 100만 달러는 아주 작은 푼돈에 불과하다. 이 문제를 풀 경우 당 해의 관련된 상이란 상은 죄다 쓸어담을 수 있을 것이니, 인생을 걸고 도전해보자.

10 암호계

참고로 모든 암호계는 [math]\text{NP}[/math] 문제이다. 적어도 비밀키를 아는 사람은 해독할 수 있어야 하므로, 비밀키가 주어지는 경우 그 비밀키가 맞는지 당연히 확인할 수 있기 때문이다. 따라서 모든 암호 해독은 [math]\text{NP}[/math] 문제일 수밖에 없고, [math]\text{P}=\text{NP}[/math]라면 거의 모든 종류의 암호는 안전할 수 없게 된다. 그래도 암호의 사용 방법을 제한해서 비밀키 하나당 암호화를 딱 한번만 하는 OTP 등이 해결책이 되겠지만 [math]\text{P}=\text{NP}[/math]라면 이마저도 조건이 까다로워져 평문 [math]n[/math] 바이트를 보내려면 비밀키 [math]n[/math] 바이트를 미리 안전한 경로로 보내야 한다.

양자컴퓨터가 주목을 받는 이유는 거대한 수의 소인수분해와 이산 로그 문제라는, 암호에서 흔히 사용되는 두 [math]\text{NP}[/math] 문제를 다항식 시간 내에 해결할 수 있기 때문이다. NP문제는 그 유래가 비결정적 튜링머신에서 나왔는데, 선택의 갈림길에서 트리를 그려서 쭈욱 진행해 나갔을 때, 마지막 결론이 있는 곳까지 도달하여 문제를 만드는 것이 NP문제의 원래 유래이다. 결정적 튜링머신에서는 이 선택의 갈림길을 동등한 입장에서 살펴볼 수 없고 반드시 이 선택들 중 주어진 알고리즘을 통해 순서대로 분석해야하지만, 양자컴퓨터는 이 비결정적 튜링머신이 하는 동등한 입장의 "선택"을 그대로 구현해주기 때문에 NP문제를 말그대로 찍어서 맞추는 방법을 찾을 수 있어 주목된다. 그러나 양자컴퓨터라고 모든 [math]\text{NP}[/math] 문제를 해결할 수 있는 것은 아니다. 소인수분해 문제와 이산 로그 문제를 제외한 [math]\text{NP}[/math] 문제들, 특히 [math]\text{NP}[/math]-완전 문제들은 현재로서는 해결할 양자 알고리즘이 없기 때문에, 지금 당장 양자컴퓨터가 실용화된다고 하더라도 대부분의 [math]\text{NP}[/math] 문제들은 풀 수 없다.

11 증명됐나?

참고로 국내의 김 모 교수가 대략 2003년부터 연말즈음 되면 이 문제를 풀었다고 언론에 나곤 했는데, 일단 못 풀었다가 정설이다. 다른 학자의 말에 의하면 이 문제에 대해서 제대로 인식하고 있는지 조차도 의심스럽다고. 이 문제가 컴공에서 비롯한 문제라 수학자들이 접근하기 위해서는 컴공에 관한 기반지식이 상당히 요구되는데 그런부분에서 신뢰할만하지 않다고. 김모 교수는 어떠한 문제가 P문제로 변환될 수 없다고 논문에서 증명했으나, 이 문제는 NP문제가 아닌 문제임이 드러났고, 학계에선 따라서 이를 인정하지 않고있다.

이후 2010년에는 인도계 미국인인 비나이 데오라리카가 증명했다고 주장하고 있다.관련 기사 하지만 논문 검증에 참여한 학자들은 이 논문에 오류가 있으며, 따라서 [math]\text{P-NP}[/math] 문제 해결에 실패했을 뿐만 아니라 중요한 진전을 이룬 점조차 없다고 평가하고 있다. 사실 [math]\text{P-NP}[/math] 문제를 해결했다는 논문은 해마다 수십 개씩 쏟아져나오고 있지만 하나같이 오류와 반례가 드러나, 아직도 별다른 진전이 없는 상태가 이어지고 있다.

어쨌든, 현재까지는 증명에 성공한 사람이 없다.

12 여담

아래의 여담(?)처럼 간단하게나마 [math]\text{P}[/math]와 [math]\text{NP}[/math]의 차이를 설명할 수는 있다. 하지만 이건 일상적인 얘기이고, 실제로는 수학적인 증명을 필요로 하는지라 아래처럼 썼다가는 다른 학자들에게 논파당하거나 비웃음거리가 되니 직관적으로만 알아두자.

• 매우 수학적으로 위의 예시를 통해 NP문제에 대해서 말할 수 있는데, "시험 볼 때 모든 문제를 찍어 맞춰서 100점을 맞을 확률이 100프로"라면, P문제인지 전혀 모르는 NP문제를 다항시간만에 풀었다고 말할 수 있으며, 이것이 실제로 양자컴퓨터에서의 NP문제를 푸는 알고리즘이다.
• 지뢰찾기를 예로 들자면, 언젠가는 여러개 중에 하나를 '찍어야 하는' 상황이 나오게 된다. 그런데 찍는다는 건 오직 비결정론적 튜링머신으로만 해결 가능하다. 결정론적 튜링머신은 읽은 데이터 하나에는 오직 하나의 명령만이 수행되기 때문이다. 난수를 쓰면 해결될 수는 있으나, 컴퓨터에서 쓰이는 난수는 의사난수이므로 다시 결정론적 튜링머신의 한계로 돌아가며, 의사난수가 아닌 난수의 생성도 비결정론적 튜링머신으로만 가능하다. 이 때문에 지뢰찾기는 NP-완전 문제로 증명된 것으로 보인다. 링크
• 이미 쿠르트 괴델이 불완전성 정리를 통해 튜링머신의 전신인 '괴델 수'가 불완전함을 증명한 바 있다. 훗날 앨런 튜링도 튜링머신을 통해 불완전성 정리를 확인한 바 있다. 결국 이 문제가 튜링머신(그리고 '괴델 수')에 묶여 있는 한 수학적인 범위 내에서 증명하는 것은 불가능에 가깝다. 이 문제를 확실하게 증명하려면 어떻게든 수학적 계산 이외의 지식을 동원해야 한다.

피노키오의 코를 잘 활용하면 풀 수 있다고 한다.

13 대중 매체에서의 등장

• Numb3rs의 주인공 수학교수가 해결하려고 매달렸던 게 이 문제다. FBI 수사관인 형이 사건해결의 조언을 구하려고 하지만 정신적 충격을 겪은 주인공이 이 문제에 다시 매달려서 외부와의 소통을 완전히 차단해버려서 고생하는 에피소드도 있다.

• 엘리멘트리 시즌 2 3화에서 이 증명을 완수한 수학자가 나온다.

• 일본의 수학 교양소설 '수학 걸 4권 - 확률적 알고리즘(Randomized Algorithms)'의 주제가 몬티 홀 문제와 NP-완전 문제이다.