P대 NP 문제

[JUN샘]

오늘날 개인용 컴퓨터(PC, Personal Computer)의 많은 수가 마이크로소프트사가 개발한 윈도(Windows)를 운영 체제로 사용하고 있다. 윈도는 가정용이나 업무용 컴퓨터, 노트북, 미디어 센터와 같은 일반 목적의 컴퓨터 시스템에서 사용할 수 있게 개발된 것으로 프로그램에 여러 가지 게임을 내장하고 있다. 그 가운데 일명 ‘지뢰 찾기’라고 하는 게임인 마인스위퍼(Mine sweeper)가 있다.

마인스위퍼에 어떤 수학이 있나?

이 게임은 마이크로소프트사의 로버트 도너와 커트 존슨이 만들었으며, 처음에는 마이크로소프트 엔터테인먼트 팩의 일부로 1990년에 출시되었다가 1992년 출시된 윈도 3.1부터는 기본으로 깔리게 되었다. 지뢰 찾기에는 기본적으로 다음과 같은 세 가지의 지뢰밭이 제공된다.       초급 : 9×9 넓이의 지뢰밭에 10개의 지뢰       중급 : 16×16 넓이의 지뢰밭에 40개의 지뢰       고급 : 30×16 넓이의 지뢰밭에 99개의 지뢰 기본적인 지뢰밭 이외에 사용자가 임의로 지뢰밭의 크기를 정하여 게임을 할 수 있도록 8×8에서 30×24 넓이의 지뢰밭에 10개에서 667개의 지뢰를 지정할 수 있다.

지뢰 찾기 게임도 NP문제에 속한다.

초급 단계에서 지뢰를 누를 확률은 흥미롭게도 0부터 9까지의 숫자를 차례로 나열한 소수이다. 즉, 아래와 같다.

또 중급과 고급에서 지뢰를 누를 확률은 40/256=0.15625과 99/480=0.20625로 수준이 올라갈수록 지뢰를 누를 확률이 높아진다. 이렇게 ‘지뢰 찾기’는 어려운 게임이지만, 인터넷에서는 고급을 30초 대, 중급을 10초에 깼다는 놀라운 기록을 담은 동영상을 쉽게 볼 수 있다. 

지뢰 찾기 게임은 P대 NP 문제의 열쇠?

격자의 어느 곳에 지뢰가 묻혀 있는지를 알아내는 단순해 보이는 이 게임이 지금까지 풀리지 않은 수학 문제는 물론 고도로 복잡한 컴퓨터 코드 해독의 열쇠가 된다면 어떨까? 영국 버밍엄 대학의 수학과 교수 리처드 케이(Richard Kaye)는 지뢰 찾기 게임의 지뢰밭의 크기를 확장함으로써 지뢰의 위치에 관한 조합을 결정하는 알고리즘을 발견할 수 있다면 지금까지 수학계의 주요 과제 중 하나인 P대 NP(P versus NP) 문제를 풀 수 있는 단서를 찾을 수 있다고 생각한 것이다. 이 P대 NP 문제는, 클레이 수학연구소(CMI, The Clay Mathematics Institute)에서 푸는 사람에게  100만 달러의 상금을 주겠다는 7개 문제 중 하나로도 유명하다.

케이 교수는 마인스위퍼 게임을 효율적으로 하는 방법이 있다면, 복잡한 인터넷 보안 코드 등 컴퓨터 코드를 효과적으로 해독하는 방법도 있을 것이라면서, 이번 발견이 난해한 수학문제해결에만 그치지 않고 컴퓨터 코드 해독에 적용되는 등 엄청난 영향력을 발휘할 수 있다고 전망했다.

P 문제는 ‘쉬운’ 문제

그렇다면 P 문제(Polynomial time problem, 다항시간문제)와 NP(Nondeterministic Polynomial time problem, 미정다항시간문제) 문제는 과연 무엇일까? P 문제는 주어진 문제를 푸는 알고리즘이 걸리는 시간이 어떤 다항식으로 나타날 때를 말한다.

 
예를 들어서 수열 5, 3, 6, 1, 4, 2를 재배열하여 1, 2, 3, 4, 5, 6가 되게 하는 방법을 생각해 보자. 이때, 재배열하는 방법은 앞에서부터 차례로 두 항을 비교해서 작은 수를 앞에 오게 하자. 이 방법을 처음부터 끝까지 적용하여 첫 번째 재배열한 것을 [단계1]이라고 하면 아래 그림에서 알 수 있듯이 모두 5번을 시행했으므로 걸린 시간을 5라고 할 수 있다.

 

[단계2]에서는 [단계1]의 마지막에 얻은 수열 3, 5, 1, 4, 2, 6으로 위와 같은 과정을 반복하여 차례로 나타내면 다음과 같다.

[단계2]는 모두 4번을 시행했으므로 걸린 시간은 4이다. 이제, 마찬가지 방법으로 다음과 같이 각 단계를 시행한다.

               

단계별로 걸린 시간을 구하면 [단계3]은 3, [단계4]는 2, [단계5]는 1이다. 그러므로 원래 수열 5, 3, 6, 1, 4, 2를 1, 2, 3, 4, 5, 6으로 바꾸는 데 걸린 시간은 모두 5+4+3+2+1=15이다. 일반적으로  개의 수열을 위와 같은 방법으로 재배열할 때 걸리는 최대시간은 다음과 같다.

결국, n의 이차식만큼의 시간이 걸렸으므로 이 문제를 푸는 데 걸리는 시간이 다항식으로 나타나므로 이 문제는 P 문제이다. 그리고 이와 같은 다항식은 풀기 쉬워서 일반적으로 P 문제는 풀기에 쉬운 문제라고 할 수 있다.

NP 문제는 ‘어려운’ 문제

대표적인 NP문제인, 해밀턴 경로 문제의 예

반면 NP 문제는 어떤 주어진 문제에 대한 답이 맞는지를 확인하는 시간이 다항식 시간만큼만 걸린다는 뜻이다. 예를 들어 68718821 377이라는 수가 어떤 두 소수의 곱이라고 할 때, 그 두 소수가 무엇인지 찾기는 쉽지 않다. 그러나 6번째와 7번째의 메르센 소수 131071과 524287의 곱이라고 말했다면 계산기만 눌러 보아도 이것이 사실인지 아닌지 간단하게 확인할 수 있다. 이처럼 처음 주어진 문제는 매우 어려워 보이지만 답이 맞는지 확인하는 과정의 횟수를 다항식으로 나타낼 수 있는 문제를 NP 문제라고 한다. 따라서 NP 문제는 풀기에는 쉽지 않지만, 답이 맞는지 확인하기는 쉬운 문제이다. NP 문제에는 해밀턴 경로 문제, 충족 가능성 문제(SAT), 외판원 문제, 그래프 색칠 문제 등 여러 가지가 있다.

예를 들어 해밀턴 경로(Hamiltonian path) 문제는 ‘어떤 그래프에서 모든 꼭짓점을 오직 단 한 번만 지나는 경로를 찾을 수 있는가?’ 하는 문제이다. 아일랜드의 수학자였던 윌리엄 해밀턴 경의 이름을 따서 이름 붙였다. 즉, 윗 그림과 같은 답을 찾는 문제인데, 이런 문제는 답을 보고 확인하기는 쉽지만 풀기는 대단히 어렵다.

P 대 NP 문제의 의미

그런데, 그림과 같이 일반적으로 모든 P 문제는 NP 문제이다. 그렇다면, 거꾸로 NP 문제이면서 P문제가 아닌 것이 존재할까? 그것을 증명하라는 문제가 바로 P대 NP 문제이다. 이는 결국 P= NP 인지 P≠NP인지 보이라는 것이다. 만일 P=NP라면 ‘어려운’ 문제는 쉽게 풀 수 있는 길이 ‘존재한다’는 의미이다. 컴퓨터의 암호 같은 것은 근본적인 원리를 따져보면 NP 문제를 이용해서 해독하기 어렵게(즉 아주 오랜 시간이 걸리게) 만들어 놓은 것이다.  그러니, P=NP라는 것이 밝혀진다면, 이런 암호를 쉽게 해독하는 길이 있다는 뜻이 되겠다.

그러나 P=NP라는 것이 밝혀진다고 해서 바로 모든 NP 문제를 쉽게 풀 수 있다는 것은 아니다. 방법이 존재한다는 것이지 그 방법 자체를 알려주는 것은 아니니까. 하지만, 쉬운 해법이 있다는 확신이 생긴다면 수 많은 사람들이 도전하여 NP 문제를 하나씩 정복해나갈 것으로 예측된다. 그러나 만일 P≠NP라는 것이 밝혀지면 그런 방법 자체가 없다는 의미가 된다. 즉, NP 문제들은 확실히 ‘어려운’ 문제로 남게 되는 것이다. 여러분이 만일 이 P대 NP문제를 해결한다면, 막대한 현상금은 물론이고 인류역사에 길이 남을 위대한 수학자가 될 것이다. 지금부터 도전해 보시길...

글 이광연 / 한서대학교 수학과 교수

성균관대학교 수학과를 졸업하고 와이오밍 대학교에서 박사후 과정을 밟았다. 저서로는 [웃기는 수학이지 뭐야], [수학자들의 전쟁], 2008년 문화체육관광부 우수과학도서로 선정된 [수학블로그] 등이 있다