최근 수정 시각 : 2019-05-12 12:55:30

P-NP 문제

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


1. 개요2. 설명
2.1. 알고리즘시간복잡도2.2. P 문제와 NP 문제
2.2.1. 이해
2.3. NP-난해 문제2.4. NP-완전 문제
3. NP 문제의 예시4. 해결된다면?
4.1. 상금4.2. 암호계4.3. 증명됐나?4.4. 수학자들의 예측
5. 여담6. 대중 매체에서의 등장

1. 개요

P versus NP problem

수학계의 최종 보스밀레니엄 문제 중 하나. 100만 달러가 걸린 문제인데, 알려진 지 40여 년이나 지났는데도 아직 풀리지 않고 있다.

P 집합과 NP 집합이 같은지 다른지를 증명하고자 한다. P집합은 이미 NP의 부분집합이므로, 모든 NP문제가 P인가를 증명하면 된다.

위 말을 일상적인 표현으로 바꾸면 "쉽게 검산할 수 있는 모든 문제들은 모두 쉽게 풀리는가?"이다. 만일 어느 한쪽으로 증명이 된다면 셋 중 하나의 결론을 도출하게 된다.
  • 같다: 쉽게 검산할 수 있는 풀기 어려운 공식은 풀기 쉬운 공식으로 변형될 수 있다.
  • 다르다: 풀기 쉬운 공식으로 변형될 수 없는 어려운 문제가 존재한다.
  • 증명할 수 없다.

2. 설명

2.1. 알고리즘시간복잡도

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

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

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

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

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

서로 다른 두 문제의 난이도를 비교하는 데에는 환원(reduction)이라고 불리는 기법이 자주 사용된다. 예를 들어, 다음의 두 가지의 문제가 주어졌다고 생각하자.
문제 A: 주어진 n개의 숫자를 크기 순서로 정렬하는 문제
문제 B: 주어진 n개 숫자의 중간값을 계산하는 문제
어떤 사람이 문제 A를 쉽게 풀 수 있다면, 그 사람은 문제 B도 쉽게 풀 수 있는 것이 당연하다. 왜냐하면 주어진 숫자들을 정렬하고 나면, 그 중 정 가운데에 있는 수를 뽑기만 하면 그것이 중간값이 될 것이기 때문이다. 이와 같은 일이 벌어진다면, 문제 B를 문제 A로 환원시킬 수 있다고 표현하며, 문제 B의 난이도는 문제 A의 난이도보다 쉽다는 것을 알 수 있다.

2.2. P 문제와 NP 문제

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

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

위의 정의는 결정적 알고리즘(deterministic algorithm), 즉 계산의 각 단계에서 단 한가지의 가능성만을 고려할 수 있는 알고리즘이 다항시간이 걸리는 문제가 P문제라는 뜻이다. NP 문제는 형식적으로는, 문제를 푸는 각 단계에서 여러가지의 가능성을 동시에 고려할 수 있는 비결정적 알고리즘(non-deterministic algorithm)으로 다항시간내에 문제를 해결할 수 있는 문제라고 정의한다. 즉 NPNon-deterministic Polynomial의 약자이다. 하지만 인간의 머리는 비결정적 알고리즘의 작동을 잘 이해 못하는 경우가 많아서인지, 검산 위주의 정의가 쓰일 때도 많다.

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

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

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

2.2.1. 이해

NP 문제에 대해 쉽게 이해하기 위해서 예를 들어보자. 어떤 그래프가 주어졌을 때, "그 그래프의 모든 점을 정확하게 한 번씩만 지나는 경로가 존재하는가?" 이를 '해밀턴 경로 문제'라고 하는데, 만약 그 답이 Yes이고 모범답안으로서 그 그래프상의 모든 점을 정확하게 한 번씩만 지나는 경로가 주어진다면, '그런 경로가 존재한다'는 것을 확인할 수 있을 것이다. 즉 적절한 모범답안이 주어진 경우 Yes라는 대답은 확인할 수 있다. 따라서 '해밀턴 경로 문제 =NP= \text{NP} 문제'이다. 그러나 그 답이 No라면, 설사 '그런 조건을 만족하지 않는 경로'가 주어진다고 하더라도 '그런 경로가 존재하지 않는다'는 것을 확인할 수는 없을 것이다. 다시 말해서 No라는 답을 다항식 시간 내에 확인할 수 있게 해 주는 종류의 모범답안은 알려져 있지 않다. 따라서 '해밀턴 경로 문제 = co-NP 문제'가 아니다. 보다 정확하게는, 'co-NP 문제'라고 증명되지 않았다. 반대로 어떤 그래프가 주어졌을 때, "그 그래프의 모든 점을 정확하게 한 번만 지나는 경로는 없는가?"라는 문제라면 이는 co-NP 문제일 것이다. [6]
  • 참고로 '바둑 같은 게임에서 필승법이 존재하는가?'는 NP 문제도 co-NP 문제도 아니다. 예컨대 바둑에서 '흑이 이기는 어떤 수순'이 주어진다고 하더라도 다른 모든 수순들을 검토해서 서로 비교하지 않는 한 그것이 '흑'에게 필승법이 존재한다는 의미인지 검증할 방법이 없다. 즉 '필승법이 존재하는가?'라는 질문에 대해서는 어떤 기보가 주어지더라도 Yes라는 대답도 No라는 대답도 다항식 시간 내에 확인할 수 없는 것이다.
  • 이와 같은 문제에서 '다항식 시간 내에' 해결 가능하다는 것은 다음과 같은 뜻이다. : 바둑판에는 19x19개의 격자가 있는데, 이 격자의 수가 xx개가 있을 때, 문제 풀이에 걸리는 시간의 최대치가 xx에 대한 다항식으로 주어진다는 뜻이다. 바둑판 문제의 경우에는 대략 x!x![7]의 경우를 확인하게 되므로, P 문제가 아니다. 이 문제는 'EXP 완전 문제'임이 증명되어 있다. 즉 이 문제를 TT의 시간 내에 풀 수 있으면 모든 지수함수적(exponential) 시간이 걸리는 문제를 'TT + 다항식' 시간 내에 풀 수 있다.

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

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

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

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

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

2.3. NP-난해 문제

임의의 문제를 다항식 시간 내에 'A' 문제로 환원(reduction 또는 transformation)할 수 있는 경우, 이 'A'문제를 'NP-난해(NP-hard) 문제'라고 부른다. 물론 NP-난해 문제 중에는 NP 문제가 아닌 것도 있다. (즉 NP보다 풀기 어려운 문제도 NP-난해 문제일 수도 있다.) 2016년 MIT 연구진이 슈퍼마리오 브라더스NP-난해 문제 임을 증명해냈다.

2.4. NP-완전 문제

NP 문제들 중에서 NP-난해 문제인 것을 가리켜 'NP-완전(NP-complete) 문제'라고 부른다. NP-완전 문제를 풀 수 있으면 모든 NP 문제를 풀 수 있게 되는 셈이므로 NP 문제들 중에서는 가장 핵심이 되는 문제들인 셈이다. 위에서 예로 든 해밀턴 경로 문제도 대표적인 NP-완전 문제들 중 하나이다. 참고로, 쿡-레빈 정리에 의해 모든 NP-완전 문제는 SAT 문제와 어려운 정도가 같다고 볼 수 있다고 한다.

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

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

3. NP 문제의 예시

  • 유명한 NP 문제 중 하나인 '거대한 자연수의 약수를 찾는 문제'의 경우를 보자. 그 자연수가 거대한 두 소수의 곱인 경우는 소인수분해를 할 방법이 알려져 있지 않다. 그러나 만약 자연수를 무작위로 뽑는 경우라면 높은 확률로 그 자연수의 약수를 적어도 하나는 찾을 수 있다. 우선 '2로 나누어질 확률'부터가 1/2이며, '2, 3, 5, 7 중 적어도 하나로 나누어질 확률'은 3/4이 넘기 때문이다. 즉 대부분의 경우에는 약수를 찾을 수 있지만 그 자연수가 거대한 두 소수의 곱인 경우에는 약수를 찾을 수 없기 때문에, (즉 약수를 찾을 수 없는 경우가 '존재'하기 때문에) 이 문제는 (현재로서는) P 문제가 아닌 것이다.
  • 외판원 순회 문제(Travelling Salesman Problem, TSP)의 경우 'NP-완전 문제'이지만, '무작위 알고리즘'을 이용하면 많은 경우에 비교적 높은 확률로 최적의 해답이나 그에 가까운 것을 찾을 수 있다. 그러나 무작위 알고리즘으로는 모든 경우에 항상 최적의 해답을 찾을 수 있는 것은 아니기 때문에 이 문제는 P 문제가 아니다.

흔히 알려진 "NP 문제 = P 문제 + NP-완전 문제"라는 공식은 옳지 않다. P 문제라고도 NP-완전 문제라고도 증명되지 않은 NP 문제들도 있기 때문이다. 대표적인 것이 '거대한 자연수의 소인수분해 문제'와 '이산 로그 문제'이다. 물론 이런 문제들이 NP-완전 문제가 아니라는 것도 증명되지 않았다.

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

2017년 9월 1일 이안 겐트 영국 세인트앤드루스대학교 교수팀이 ‘8퀸 문제’를 일반화한 ‘N-퀸 완전 문제’가 NP-완전에 속한다고 발표하면서 무려 10억 원의 상금이 걸린 체스 문제가 탄생했다. N-퀸 문제는 크기 n×n 체스판에 을 배치하는 문제다. 규칙은 간단한데, 체스판 위의 모든 퀸이 서로를 공격하지 않는 위치에 놓는 것이다. 물론 이 때 쓰이는 퀸의 말은 최소한이어야 한다.[14]2x2, 3x3, 4x4 까지는 풀어줄만 하지만 8x8부터는 풀기가 만만치 않다.

4. 해결된다면?

4.1. 상금

이 문제는 100만 달러가 걸린 밀레니엄 문제 중 하나긴 하나 이 문제에 걸린 세계적인 명성에 비하면 100만 달러 따위는 푼돈이라 할 정도다.

PNP라는 것을 증명했을 경우 당신의 이름이 수학, 통계학, 암호학 관련 분야의 전공 교과서에 실리게 될 것이다.

만에 하나 P=NP라는 것을 증명이라도 하는 날이면 대학교 교과서는 말할 것도 없고, 꼬꼬마들 보는 위인전에도 당신의 이름이 실리게 된다. NP문제 중에서는 이론적, 실용적으로 상당히 중요한 문제들이 많은데(예컨대, 후술하겠지만 암호화 알고리즘들은 NP 문제에 의존한다.) 이런 문제에 효율적인 솔루션이 발견될 수 있다는 의미가 되기 때문이다.[15] 맞다는 증명이 성공할 경우 당 해의 관련된 상이란 상은 죄다 쓸어담을 수 있을 것이며 엄청나게 비싼 강연 요청이 전 세계에서 쇄도할 것이다. 아니, 어쩌면 그 사람 이름을 따서 튜링 상이나 노벨상에 버금가는 위상의 새로운 상이 만들어질지도 모른다.

4.2. 암호계

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

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

4.3. 증명됐나?

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

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

교수팀이 선보인 문제는 N개 중 일부가 이미 자리를 잡고있을 때, 나머지를 올려놓는 방법에 대한 것인데, 문제는 반복되는 규칙이 없어 슈퍼컴퓨터로 일일이 퀸의 위치를 대입해도 답을 찾는 데 수천 년이 걸리게 되며 교수팀은 이 문제가 NP-완전 이라는 걸 밝혔다. 따라서 만약 이 문제를 다항 시간 안에 푸는 알고리즘을 만든다면 ‘P=NP’라는 수학계 7대 난제를 해결하는 셈이 되므로, 미국 클레이 수학연구소가 주는 상금을 받을 수 있게 된다.

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

4.4. 수학자들의 예측

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

물론 믿음과 증명은 별개이므로, P=NP라고 믿고 있는 수학자들도 존재한다.

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

5. 여담

아래의 여담(?)처럼 간단하게나마 PNP의 차이를 설명할 수는 있다. 하지만 이건 일상적인 얘기이고, 실제로는 수학적인 증명을 필요로 하는지라 아래처럼 썼다가는 다른 학자들에게 논파당하거나 비웃음거리가 되니 직관적으로만 알아두자.
  • 매우 수학적으로 위의 예시를 통해 NP문제에 대해서 말할 수 있는데, "시험 볼 때 모든 문제를 찍어 맞춰서 100점을 맞을 확률이 100프로"라면, P문제인지 전혀 모르는 NP문제를 다항시간만에 풀었다고 말할 수 있으며, 이것이 실제로 양자컴퓨터에서의 NP문제를 푸는 알고리즘이다.
  • 지뢰찾기를 예로 들자면, 언젠가는 여러개 중에 하나를 '찍어야 하는' 상황이 나오게 된다. 그런데 찍는다는 건 오직 비결정론적 튜링머신으로만 해결 가능하다. 결정론적 튜링머신은 읽은 데이터 하나에는 오직 하나의 명령만이 수행되기 때문이다. 난수를 쓰면 해결될 수는 있으나, 컴퓨터에서 쓰이는 난수는 의사난수이므로 다시 결정론적 튜링머신의 한계로 돌아가며, 의사난수가 아닌 난수의 생성도 비결정론적 튜링머신으로만 가능하다. 이 때문에 지뢰찾기는 NP-완전 문제로 증명된 것으로 보인다. 링크
  • 이미 쿠르트 괴델불완전성 정리를 통해 튜링머신의 전신인 '괴델 수'가 불완전함을 증명한 바 있다. 훗날 앨런 튜링도 튜링머신을 통해 불완전성 정리를 확인한 바 있다. 결국 이 문제가 튜링머신(그리고 '괴델 수')에 묶여 있는 한 수학적인 범위 내에서 증명하는 것은 불가능에 가깝다. 이 문제를 확실하게 증명하려면 어떻게든 수학적 계산 이외의 지식을 동원해야 한다.
  • 참고로, PNP라면, natural proof 등에 기반한 증명은 이 문제를 증명할 가능성이 희박함이 증명되어 있는데, 사람이 만든 증명은 natural proof를 피해가기 어렵다고 한다.알파고를 써보자!!
  • P-NP 문제가 풀리면 마치 모든 수학적 문제가 알고리즘을 통해 해결될 수 있다는 것처럼 오해하는 사람이 많고, 당장 나무위키의 본 문서에도 그런 오해가 진실인 것처럼 쓰여 있기도 했다. 그러나 이는 오해로, 애초에 정지 문제 등을 통해 알 수 있듯, 모든 수학적 문제를 기계적 알고리즘으로 해결할 방법은 없다는 것이 이미 증명됐다. 그냥 그런 방법이 발견되지 않은 정도가 아니라 원론적으로 불가능하다는 것이다. 거의 컴퓨터 공학 역사의 초기에 증명된 것들 중 하나로, 이 메타 정리는 1936년에 알론조 처치와 앨런 튜링에 의해 각각 증명되었다.

피노키오의 코를 잘 활용하면 풀 수 있다고 한다. 피노키오 : 거짓이라고 했지 오류라고 한 적 없는데요

6. 대중 매체에서의 등장

  • Numb3rs의 주인공 수학교수가 해결하려고 매달렸던 게 이 문제다. FBI 수사관인 형이 사건해결의 조언을 구하려고 하지만 정신적 충격을 겪은 주인공이 이 문제에 다시 매달려서 외부와의 소통을 완전히 차단해버려서 고생하는 에피소드도 있다.
  • 엘리멘트리 시즌 2 3화에서 이 증명을 완수한 수학자가 나온다.
  • 마인크래프트의 시작 화면의 스플래쉬에서 'NP is not in P!'라는 문구가 뜬다.어떻게 아는거야


[1] 단 여기서 말한 곱셈은 말 그대로 손으로 곱셈하는 알고리즘일때의 얘기다. 실제로는 두 정수의 곱셈 알고리즘의 경우 가장 대표적이면서 처음으로 O(n2)O(n^2) 보다 빨랐던 Karatsuba 알고리즘이 O(nlog3)O(n^{\log 3}) 정도이다. 이후 Schönhage–Strassen 알고리즘, Fürer 알고리즘 등이 나오면서 복잡도는 더 개선되고 있다. 단, 이 알고리즘들은 매우 큰 수에 대해서만 더 효율적이다. 알고리즘 과정 자체에 필요한 side-effect 비용으로 인해서 작은 수의 곱셈에서는 O(n2)O(n^2) 알고리즘이 더 효율적이다. 마찬가지로 앞에서 언급한 더 개선된 알고리즘들은 복잡도는 개선되었지만 실제로 효율이 더 좋아지는 수의 하한은 더욱 커진다.[2] 대소문자 구분 없음. 주어진 자릿수로만 나옴.[3] 대략 3.1429 * 10^142 정도[4] 물론 먼 미래에는 가능할 수 있겠지만 그래도 위의 141조의 시행을 대략 2.2264 * 10^127 번 더 해야 한다.[5] 소인수분해의 어려움은 널리 쓰이는 RSA 암호 시스템의 밑바탕이 된다. 기존의 컴퓨터들과는 조금 다른 메커니즘으로 동작하는 양자컴퓨터를 사용한다면 소인수분해를 다항식 시간에 계산할 수도 있지만, 알다시피 양자컴퓨터는 아직 상용화되지 않았다.[6] 참고로 해밀턴 경로 문제가 바로 NP-완전 문제로, 이게 P 문제라는 걸 증명하거나 P 문제가 아니라는 걸 증명하면 당신은 이 문제를 해결 한 것이므로 검증 밎 여러 수순만 제대로 거치면 당신은 평생 손가락 하나 까딱 안해도 살 수 있는 부자가 된다.[7] '대략'인 이유는 착수 금지인 자리도 있지만, 돌을 따내고 그 자리에 다시 놓는 것이 가능하기 때문.[8] 참고로 그 역은 아직 증명도 반증도 되지 않았다. 즉 'NP 문제이면서 동시에 co-NP 문제이지만 P문제가 아닌 문제가 존재하는가' 역시 지금으로서는 알 수 없고, 몇몇 후보만 거론되고 있다.[9] 당연히 모든 경우에서 0q0 \leq q이다.[10] 여기서 못한다는 말은 P 알고리즘을 그대로 NP에 적용하는 경우를 말하는 것이다. NP 알고리즘이라 해도 P보다 엉망으로 짜면 오히려 결과가 안 좋을 수도 있다.[11] 0\aleph_0의 자연수 제곱은 모두 0\aleph_0이다. 해당 문서의 '자연수 vs 유리수' 부분을 볼 것.[12] 즉,1\aleph_1이나 2\aleph_2 이상 규모의 시간복잡도가 나온 경우[13] '증명 불가능'이 증명되어도 그 결론을 이끄는 논리에 오류가 없다면 '증명'한 것으로 인정된다. 지금까지 '증명'한 학자가 없는 건 논리에 오류가 드러났기 때문.[14] 퀸은 상하좌우뿐만 아니라 대각선까지 모든 방향으로 움직이기 때문에 어떤 퀸이 다른 퀸을 공격하지 못하게 막으려면 모든 퀸이 서로 다른 가로줄, 세로줄, 대각선에 있어야 한다.[15] 물론, P=NP라고 해서 모든 문제가 해결되는 것은 아니다. 다항식 시간이 걸리는 알고리즘이 존재한다는 것이지, 이 알고리즘이 무엇인지에 대한 정보는 주지 않기 때문이다. 하지만, 많은 학자들이 이에 대해 연구할 것이다. 물론, P≠NP여도 소인수 분해와 같은 문제를 다항식 시간 내에 해결하는 알고리즘이 발견될 수도 있다.[16] 역은 성립하지 않는다. 암호계에서 사용되려면 '최악의 경우'가 아니라 '평균적인 경우'에 다항식 시간 내에 풀 수 없는 NP 문제일 필요가 있다.