mir.pe (일반/밝은 화면)
최근 수정 시각 : 2024-09-20 11:56:02

P-NP 문제

P-NP에서 넘어옴
이산수학
Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" 		이론
<colbgcolor=#3CC> 기본 대상 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합 경우의 수( 공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타 P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 }}}}}}}}}


''' 이론 컴퓨터 과학
{{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px" 		<colbgcolor=#a36> 이론
기본 대상 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론 FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어
계산 복잡도 이론 점근 표기법 · 튜링 기계^ 고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법)
정보이론 데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어이론 프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초 정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^ 힙, 피보나치 힙^
수학적 최적화 조합 최적화 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화 내부점 방법 · 경사하강법
선형계획법 심플렉스법
계산 수론 및 암호학 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호
대칭키 암호화 방식 블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
공개키 암호화 방식 공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
그래프 이론 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제 대각선 논법 · 암달의 법칙 · 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

컴퓨터과학, 수학계의 최종 보스인 밀레니엄 문제 중 하나로, P 집합과 NP 집합이 같은지 다른지를 증명해야 하는 문제다. P 집합은 이미 NP의 부분집합이므로, 모든 NP 문제가 P 문제라는 것을 밝히면 P 집합과 NP 집합은 같은 것이 된다. 1971년에 처음 제시되어 50여 년이 지났음에도 아직 풀리지 않고 있다.

위 말을 일상적인 표현으로 바꾸면 "쉽게 검산할 수 있는 모든 문제들은 모두 쉽게 풀리는가?"이다. 만일 어느 한쪽으로 증명이 된다면 셋 중 하나의 결론을 도출하게 된다.
수학 문제지만 알고리즘의 관점으로도 접근할 수 있기 때문에, 컴퓨터과학 분야의 영역에도 해당하는 문제이며 컴퓨터과학을 전공한다면 대학에서 배울 수도 있다. 다만 트랜지스터의 P-NP와는 전혀 무관하니 혼동하지 말자.

이 문제를 풀게 되면 컴퓨터과학, 수학 발전에 엄청난 공헌을 한 사람으로 역사에 길이 기억될 것이다. '수학계의 노벨상'이라 불리는 필즈상을 사실상 예약해 놓을 정도이고[2] '컴퓨터과학계의 노벨상'이라 불리는 튜링상도 수상할 가능성이 있다.

2. 설명

2.1. 알고리즘의 시간 복잡도

컴퓨터를 이용해 특정한 계산 문제를 풀기 위해서는 그 문제에 해당되는 알고리즘을 컴퓨터에게 알려주어야 한다. 하지만 충분히 짧은 시간 안에 작동하지 않는 비효율적인 알고리즘은 실용성이 없을뿐더러 어떠한 학문적 흥미도 끌지 못한다. 예를 들어 어떤 알고리즘이 결과값을 도출하는데 까지 [math({10}^{12})]초가 걸린다고 가정해보자. 이를 년으로 환산하면 약 31,689년이다. 이런 경우 우리 인간은 물론이고 컴퓨터도 연산이 끝날때까지 살아남아 있지 못할 것이다. 따라서 컴퓨터과학자들의 주된 관심사는 알고리즘이 특정 문제를 얼마나 빨리 해결할 수 있느냐에 집중되어 있다.

물론 알고리즘에 입력한 자료의 크기가 커질수록 일반적으로 알고리즘의 수행 시간은 점점 오래 걸린다. 예를 들어 어떤 컴퓨터가 숫자 100개를 더하는 문제를 푸는 데 100 나노초가 걸렸다면, 이 컴퓨터가 숫자 1000개를 더하는 문제를 풀 때는 1000 나노초가 소요될 것임을 어렵지 않게 짐작할 수 있다. 다시 말해서 "숫자 [math(n)]개를 모두 더하는 연산은 약 [math(n)] 나노초가 소요된다"라고 일반적으로 표현할 수 있는 것이다. 컴퓨터과학에서는 알고리즘의 시간복잡도를 [math(\mathcal{O}(n))]이라고 표기하는데, [math(mathcal{O})]라는 표시는 간단히 말해 [math(n)] 앞에 곱해질 비례상수는 신경 쓰지 않겠다는 의미다. 어떤 문제가 [math(\mathcal{O}(n))] 알고리즘을 가진다는 것은 그 문제가 컴퓨터에게 아주 쉬운 문제라는 것을 의미한다.

조금 더 복잡한 문제를 생각해보자. 만약 [math(n)]자리의 두 자연수를 곱해야 한다면 얼마나 많은 계산이 필요할까? 컴퓨터 없이 손으로 이를 푼다고 가정해보면, 그 중간 과정에서는 [math(n)]개의 행이 필요할 것이고, 각각의 행은 다시 [math(n)]개의 숫자로 구성되어 있을 것이다. 그러므로 [math(n)]자리의 두 자연수를 곱하는 문제를 손으로 푸는 건 거의 [math(n^2)]에 비례하는 시간이 필요하다. 이때는 알고리즘의 시간복잡도가 [math(\mathcal{O}(n^2))]가 된다. 즉, 100자리 수의 곱셈을 하는 것은 10자리 수의 곱셈을 하는 것보다 10배가 아닌 100배나 어려운 문제라는 것이다. 따라서 곱셈은 덧셈보다는 비교적 어려운 문제라는 결론을 도출할 수 있다.

만약 대소문자 구별 없는 a~z까지의 로마자 알파벳(26가지)을 무작위로 골라 만든 10자리의 비밀번호를, 모든 가능성을 다 대입해봄( 브루트 포스)으로써 알아내고자 한다면 얼마나 많은 시도가 필요할까? 잘 알다시피 최대 [math(26^{10})], 즉 약 141조 번에 달하는 수많은 시도가 필요하다. 하지만 현대의 슈퍼컴퓨터를 동원하면 이 정도의 작업은 가능한 일의 범위 안에 있다. 그렇다면 상황을 더욱 극단적으로 만들어서, 100자리의 비밀번호를 이러한 방식으로 풀려면 얼마나 많은 시도가 필요할까? [math(26^{100})]은 10의 112제곱인 긍갈라보다도 몇십 양배나 큰 수[3]다. 이때의 시간복잡도는 [math(\mathcal{O}(26^n))]으로, 이 문제는 [math(n)]자리 수의 곱셈과는 차원이 다른, 규모를 헤아리기조차 힘들 만큼 어마어마하게 어려운 문제임을 알 수 있다.

앞의 쉬운 문제 두 개와 뒤의 어려운 문제의 차이점은 간단하다. 앞의 문제들에 대한 알고리즘은 [math(\mathcal{O})]의 괄호 안에 들어있는 식이 [math(n)]에 대한 '다항식'이었고, 뒤의 어마어마하게 어려운 문제는 [math(\mathcal{O})]의 괄호 안에 [math(n)]에 대한 '지수함수'가 들어 있다는 것이 중요한 차이점이다. 물론 다항식도 [math(n)]이 커지면 값이 증가하지만 그것은 지수함수의 것에 비하면 새 발의 피에 불과하다. 다시 말해 다항식 시간 알고리즘이 존재하는 문제는 고성능 컴퓨터를 통하면 비교적 원활히 해결할 수 있는 쉬운(tractable) 문제고, 다항식 시간 알고리즘이 존재하지 않는 문제는 온 우주가 힘을 모아도 푸는 게 불가능할 수 있는 어려운(intractable) 문제다. 이를 통해 우리는 어떤 문제가 쉬운지 어려운지를 판별할 수 있다.

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

서로 다른 두 문제의 난이도를 비교하는 데에는 환원(reduction)이라는 기법이 자주 사용된다. 예를 들어, 다음 두 가지 문제를 보자.
문제 A: 주어진 [math(n)]개의 숫자를 크기 순서로 정렬하는 문제
문제 B: 주어진 [math(n)]개 숫자의 중앙값을 계산하는 문제
어떤 사람이 문제 A를 쉽게 풀 수 있다면, 그 사람은 문제 B도 쉽게 풀 수 있다는 걸 직관적으로 알 수 있을 것이다. 다시 말해, 문제 B의 난이도는 문제 A의 난이도보다 어려울 수 없다. 주어진 숫자들이 정렬됐다면, 그중 정가운데에 있는 수를 뽑기만 해도 문제 B가 해결되기 때문이다. 이를 "문제 B를 문제 A로 환원시킬 수 있다"고 표현한다.

2.2. P 문제와 NP 문제

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

P 문제는 결정 문제들 중 쉽게 풀리는 것을 모아 놓은 집합이다. 어떤 결정 문제가 주어졌을 때, 다항식(Polynomial) 시간 이내에 그 문제의 답을 계산해낼 수 있는 알고리즘이 존재한다면, 그 문제는 P 문제에 해당된다. 이 정의는 결정적 알고리즘(deterministic algorithm), 즉 계산의 각 단계에서 단 한 가지의 가능성만을 고려할 수 있는 알고리즘이 다항 시간이 걸리는 문제가 P 문제라는 뜻이다. 상술한 'a는 b의 배수인가?'라는 질문은, [math(n)]자리 이하의 수 a와 b가 주어졌을 때 유클리드 호제법을 사용하면 [math(n)]에 대한 다항식 시간에 계산할 수 있어 P 문제에 해당된다.

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

NP 문제는 결정 문제들 중에서 적어도 검산은 쉽게 할 수 있는 것을 모아 놓은 집합으로도 정의할 수 있다. 정확히 말하면, 어떤 결정 문제의 답이 YES일 때, 그 문제의 답이 YES라는 것을 입증하는 '힌트'가 주어지면, 그 힌트를 사용해서 그 문제의 답이 정말로 YES라는 것을 다항식 시간 이내에 확인할 수 있는 문제가 바로 NP 문제에 해당된다. 예를 들어, [math(\{-5,\,6, \,1,\,2,\,-10,\,-7,\,13\})]과 같이 정수 [math(n)]개로 이루어진 집합이 주어졌다고 할 때, '이 집합의 부분집합들 중에서 원소의 합이 [math(0)]이 되는 집합이 존재하는가?'라는 문제는 아직까지 다항식 시간 알고리즘이 알려져 있지 않다.[4] 곰곰이 생각해봐도, 그냥 모든 부분집합을 다 테스트해보지 않는 이상 답이 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 문제이다. 이를 도식화 해보면 다음 그림과 같다.

파일:4-12-5.png

2.2.1. 이해

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

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

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

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

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

2.3. NP-난해 문제

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

2.4. NP-완전 문제

NP-난해임과 동시에 NP인 문제, 즉 모든 NP 문제를 환원[10]시킨 문제가 다시 NP가 될 때, 그 문제를 'NP-완전(NP-complete) 문제'라고 부른다. NP-완전 문제를 풀 수 있으면 모든 NP 문제를 풀 수 있게 되는 셈이므로 NP 문제들 중에서는 가장 핵심이 되는 문제들인 셈이다. 위에서 예로 든 해밀턴 경로 문제도 대표적인 NP-완전 문제들 중 하나이다. 참고로, 쿡-레빈 정리에 의해 모든 NP-완전 문제는 SAT[11] 문제와 어려운 정도가 같다고 볼 수 있다고 한다.

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

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

3. NP 문제의 예시


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

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

2017년 9월 1일 이안 겐트 영국 세인트앤드루스대학교 교수팀이 여덟 퀸 문제를 일반화한 'N-퀸 완전 문제'가 NP-완전에 속한다고 발표하면서 무려 10억 원의 상금이 걸린 체스 문제가 탄생했다. N-퀸 문제는 크기 n×n 체스판에 n개의 퀸을 서로 공격하지 않는 위치에 배치하는 문제다. 규칙은 간단하지만 8x8부터는 풀기가 만만치 않다.[14][15] 교수팀이 선보인 문제는 N개 중 일부가 이미 자리를 잡고 있을 때, 나머지를 올려놓는 방법에 대한 것이다. 문제는 반복되는 규칙이 없어 슈퍼컴퓨터로 일일이 퀸의 위치를 대입해도 답을 찾는 데 수천 년이 걸리게 되며, 교수팀은 이 문제가 NP-완전이라는 걸 밝혔다. 따라서 만약 이 문제를 다항 시간 안에 푸는 알고리즘을 만든다면 'P=NP'라는 결론과 함께[16] 수학계 7대 난제 중 하나를 해결하는 셈이 되므로, 미국 클레이 수학연구소가 주는 상금을 받을 수 있게 된다.

4. 해결된다면?

4.1. 상금과 명예

이 문제는 100만 달러가 걸린 밀레니엄 문제 중 하나이지만, 이 문제를 해결함으로써 얻을 세계적인 명성에 비하면 100만 달러 따위는 푼돈이라 할 정도다. P≠NP라는 것을 증명했을 경우 당신의 이름이 수학, 컴퓨터과학, 암호학 관련 분야의 대학교 전공 교과서에 길이 실리게 될 것이다.

만에 하나 P=NP라는 것을 증명이라도 하는 날이면 P≠NP 증명 이상의 명성이 남게 될 가능성이 높다. NP 문제 중에서는 이론적, 실용적으로 상당히 중요한 문제들이 많은데[17], 이런 문제에 효율적인 솔루션이 발견될 수 있다는 의미가 되기 때문이다.[18] 맞다는 증명이 성공할 경우 컴퓨터과학계의 노벨상인 튜링상 및 나이를 만족한다면 수학계의 노벨상인 필즈상[19] 등 수학 관련 상을 다수 수상할 것이다.

4.2. 암호계

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

양자컴퓨터가 주목을 받는 이유는 거대한 수의 소인수분해와 이산 로그 문제라는, 암호에서 흔히 사용되는 두 NP 문제를 다항식 시간 내에 해결할 수 있기 때문이다. 그러나 양자컴퓨터라고 모든 NP 문제를 해결할 수 있는 것은 아닐 것으로 추정된다. 소인수분해 문제와 이산 로그 문제를 제외한 NP 문제들, 특히 NP-완전 문제들은 현재로서는 해결할 양자 알고리즘이 없기 때문에, 지금 당장 양자컴퓨터가 실용화된다고 하더라도 대부분의 NP 문제들은 풀 수 없다.

4.3. 증명됐나?

참고로 전북대학교의 김모 교수가 대략 2003년부터 연말 즈음 되면 이 문제를 풀었다고 언론에 내곤 했는데, 일단 '못 풀었다'가 정설이다. 다른 학자의 말에 의하면 이 문제에 대해서 제대로 인식하고 있는지조차도 의심스럽다고. 이 문제가 전산학, 컴퓨터 과학 분야에서 비롯한 문제라 수학자들이 접근하기 위해서는 전산학, 컴퓨터 과학 분야에 관한 기반 지식이 상당히 요구되는데, 그런 부분에서 신뢰할 만하지 않다고 한다. 이에 대하여 김 모 교수는 반박하고 있다. 보여준 문제가 np문제가 아니라는 것은 거짓이라고. 그 문제가 np문제이지만 p문제는 아니라는 내용을 123쪽에 달하는 논문에 담아 arXiv에 게재하였다고 한다.

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

아직까지 공식적으로는 아무도 올바른 증명을 찾아내지 못하였고, 이것을 증명하는 것이 왜 어려운 일인지를 암시하는 간접적인 결과만이 조금 밝혀져 있을 뿐이라고 생각된다.

4.4. 학계의 예측

사실 많은 학자들은 P≠NP일 것이라고 믿는다. 이유는 간단한데, 수많은 학자들이 여러 NP 문제들에 대해서 '다항식 시간 내에 풀 수 있는 알고리즘'을 찾으려고 노력해 왔지만 전혀 성과가 없었기 때문이다.

또다른 이유로는, 임의의 명제를 증명하는 문제는 P이고, 검증하는 문제는 NP인데, 증명은 검증보다 본질적으로 어려운 문제일 것이므로 NP와 P가 같을 수 없다는 믿음이 있다. P=NP가 의미하는 바란, 만약 어떤 문제가 주어졌을 때 그 문제의 답안을 쉽게 검산할 수 있다면 그 문제 자체도 쉽게 풀 수 있다는 대단히 강력한 주장인데, 이는 우리가 지금까지 열심히 수학을 공부하면서 몸에 체득해온 직관과 배치되는 일이다. 일부 방정식의 경우 해를 직접 구하는 것은 어렵지만, 남이 미리 풀어서 구한 답을 방정식에 대입해서 그게 맞는지 확인하는 일은 훨씬 쉬운 경우가 많다.

설문조사 결과에 따르면, 2002년에 이론전산학자 100명을 대상으로 한 설문조사에서는 "P≠NP"일 것이라고 답하는 비율이 61%, "P=NP"은 9%, "대답할 수 없음 혹은 증명이 불가능함"은 30%였다.

5. 여담

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

6. 대중 매체에서

[1] "증명할 수 없다"는 것을 증명해야 된다는 뜻. [2] 만 40세 미만이라면 받을 수 있다. 그런데 이 정도 급의 문제를 해결한다면 40세가 넘더라도 와일스 교수처럼 나이 따위 무시하고 특별상을 줄 가능성이 더 높다. [3] 대략 [math(3.1429\times10^{141})] 정도. 정확한 값은 3142930641582938830174357788501626427282669988762475256374173175398995908420104023465432599069702289330964075081611719197835869803511992549376 [4] 동적 계획법(dynamic programming) 알고리즘 설계법을 이용하면, 원소의 개수 [math(N)], 정수 원소의 범위 [math(M)]이 특정됐을 때 [math(N)]과 [math(M)]에 비례한 유사-다항함수 시간 내에 해결할 수 있다. [5] co-NP 문제는 NP 문제에 대한 보완(complement)으로, 적절한 힌트가 주어진 경우 결정이 No라는 것을 다항식 시간 내에 알 수 있는 문제이다. 보완 문제(complement problem)은 원래 문제의 반대로, 원래 문제가 '주어진 그래프에 해밀턴 경로가 존재하는가?'라면, '주어진 그래프에 해밀턴 경로가 존재하지 않는가?'가 보완 문제가 된다. 즉, 원래 문제와 보완 문제의 답변은 반대가 된다. [6] 참고로 해밀턴 경로 문제가 바로 NP-완전 문제로, 이게 P 문제라는 걸 증명하거나 P 문제가 아니라는 걸 증명하면 당신은 이 문제를 해결한 것이므로 검증 밎 여러 수순만 제대로 거치면 당신은 평생 손가락 하나 까딱 안해도 살 수 있는 부자가 된다. [7] 참고로 그 역은 아직 증명도 반증도 되지 않았다. 즉, 'NP 문제이면서 동시에 co-NP 문제이지만 P문제가 아닌 문제가 존재하는가?'는 역시 지금으로서는 알 수 없고, 몇몇 후보만 거론되고 있다. [8] 당연히 모든 경우에서 [math(0 \leq q)]이다. [9] 여기서 못한다는 말은 P 알고리즘을 그대로 NP에 적용하는 경우를 말하는 것이다. NP 알고리즘이라 해도 P보다 엉망으로 짜면 오히려 결과가 안 좋을 수도 있다. [10] 다항식 시간 내로. [11] '충족 가능성 문제'로, 미국의 대학 입시 문제하고는 관련 없다. [12] 결정론적 튜링머신으로 평균적으로 다항식 시간 내에 해결할 수 있는 문제의 집합은 ZPP에 해당된다. [13] P≠NP일 경우, 이 문제는 P도 아니고 NP-완전도 아닌 NP-중간(NP-intermediate) 문제일 것으로 추정되고 있다. [14] 8-퀸 문제는 수수께끼 풀이 게임으로 유명한 레이튼 교수 시리즈에서 최고난도 컨텐츠로 삽입되어있다. [15] 단, 퀸이 미리 배치되지 않은 경우 해답 중 하나를 구하는 것은 선형 시간에 가능하다. [16] 그리고 만약 이 문제를 다항시간 내에 풀 수 있는 알고리즘이 존재하지 않는다는 사실을 증명한다면 'P≠NP'라는 결론이 도출되므로 이 또한 P-NP 문제를 해결란 셈이 된다. [17] 예컨대, 후술하겠지만 암호화 알고리즘들은 NP 문제에 의존한다. [18] 물론, P=NP라고 해서 모든 문제가 해결되는 것은 아니다. 다항식 시간이 걸리는 알고리즘이 존재한다는 것이지, 이 알고리즘이 무엇인지에 대한 정보는 주지 않기 때문이다. 하지만 많은 학자들이 이에 대해 연구할 것이다. 물론 P≠NP여도 소인수분해와 같은 문제를 다항식 시간 내에 해결하는 알고리즘이 발견될 수도 있다. [19] 40세를 경과하더라도 300년의 난제를 해결한 앤드루 와일스처럼 특별상이 수여될 수는 있으나, 해당 특별상은 정식 수상자에 포함되지는 않는다. [20] 역은 성립하지 않는다. 암호계에서 사용되려면 '최악의 경우'가 아니라 '평균적인 경우'에 다항식 시간 내에 풀 수 없는 NP 문제일 필요가 있다. [21] 컴퓨터로는 의사 난수만 생성한다고 잘못 생각할 수 있는데, 특수 장비를 사용해서 진짜 난수를 생성하는 것도 얼마든지 가능하다. 그리고 의사 난수를 사용하더라도 컴퓨터는 대부분의 확률 문제를 풀 수 있다. 몬테카를로 시뮬레이션을 돌릴 때도 특수한 경우가 아닌 이상 일반적으로 쓰는 의사난수를 사용한다. [22] NP-완전 문제를 다항시간 안에 푸는 결정론적 알고리즘이 제시되는 방식으로

분류