길거리의 행인을 위한 
백만불 현상 문제 소개: P = NP ?

2001년 1월 (대한수학회 소식지 원고)
서울대학교 김홍종

미국의 실업가인 Landon Clay 는 새천년을 기념하여 미국의 Cambridge 에 있는 Clay 수학연구소(Clay Mathematics Institute, http://www.claymath.org)를 세우고, 저명한 수학자 Alan Connes, Arthur Jaffe, Andrew Wiles, Edward Witten 등의 조언을 구하여 2000년 5월24일 각각 백만불 현상금이 붙은 미해결 수학문제 일곱개를 발표하였다. 발표한 도시는 프랑스의 파리로 그곳은 백년전 제2회 국제수학자 대회에서 David Hilbert(1862--1943)가 새로운 세기를 위한 스물세가지 문제를 제시하였던 곳이다. 물론 Clay 수학연구소에서 제시한 문제 외에도 중요하고 좋은 문제들이 많이 있으며 같은 정도의 현상금이 붙은 문제들도 있다.

서울대학교에서는 학부제와 대학원 중심제로 인하여 의욕을 잃고 방황하는 대학생들에게 활기를 불어 넣어 주고 수학을 널리 홍보하기 위하여 강현배 교수의 조직으로 지난해 12월 1일 "새천년 수학문제 소개회"를 열어 Clay 수학연구소의 일곱문제 중 네 문제를 소개하였다. 먼저 아주대학교의 이중섭 교수는 정수론이나 복소함수론 등과 관련한 "Riemann 가설"을 소개하였고, 이어서 서울대학교의 채동호 교수가 유체역학과 비선형 편미분 방정식론에서 중요한 "Navier-Stokes 방정식"을, 최서영 교수는 삼차원 공간의 위상에 관한 "Poincar'e 예상"을 소개하였으며, 마지막으로 필자가 계산과학의 문제인 "P 대 NP"를 소개하였다. 필자가 발표자가 된 까닭은 다른 문제를 소개하기로 하였던 강사가 사정이 생겨 급히 메꿔야 할 빈 자리가 생겼기 때문이었다.  세상에 부족한 것을 채울 수 있다면 존재이유를 정당화 할 수 있으리라. 세상이 필요로 하는 것이 없다면 감사의 기도를 하리라.

"P 대 NP" 문제는 일곱문제 중에서 일반 대중이 가장 이해하기 쉬운 문제인 것 같다. 비록 그 풀이는 그렇지 않을 수 있지만.

▒▒▒ 넓은 의미의 알고리듬 ▒▒▒

요즈음에는  알고리듬이라는 단어를 훨씬 포괄적인 의미로 사용한다.  300원짜리 커피를 파는 자동판매기의 내부에도 간단한 알고리듬이 있어서, 적합한 금액이 들어오면 프림/설탕의 선택에 따라 종이컵과 따끈한 커피를 내놓고 거스름 돈도 정산하여 준다. 높은 아파트에 사는 사람이 출근하려고 엘리베이터 단추를 누르면, 엘리베이터를 작동시키는 알고리듬은 다른 층에 사는 사람이 부르는 지 등을 판정하여 적절한 움직임을 한다.  그러나 알고리듬이 부실하게 짜여 있으면, 자동판매기가 이상하게 행동하고, 엘리베이터가 고장이 난다.  차량 소통이 원할하도록 교통신호등 체계에 대한 알고리듬을 짜는 것과 아무렇게나 신호등을 설치하는 것은 우리 생활에 커다란 차이를 준다.

맛있는 요리법을 잘 적은 지침도 알고리듬이요, 카드 놀이나 바둑, 장기, 운동 경기의 규칙도 알고리듬이요, 최첨단 컴퓨터가 작동하는 프로그램도 알고리듬이며, 학교가 학생을 선발, 교육하고 졸업시키는 과정도 그렇고, 국가의 여러 가지 정책도 알고리듬이다. 최근에는 생물들의 DNA에서 A, G, C, T 염기로 이루어진 서열이 바로 스무가지 아미노산을 만들고 단백질의 생성을 통제하는 알고리듬이라는 것이 밝혀짐에 따라  다윈의 생물 진화에 대한 `자연선택'이나 사람과 동물의 두뇌 활동까지도 알고리듬을 뜻하는 것으로 이해하고 있다.

넓은 의미의 알고리듬이란 개인의 감정이나 사용하는 주체 등과 상관없는 `순수한 논리적 과정'으로 `분명한 결과'를 내는 것을 뜻한다 [Dennet]. 바른 알고리듬은 그 지침이 명백하여 누구라도 따라 할 수 있도록 짜여져 있는 논리적 과정이다.  [Knuth] 는 알고리듬의 중요한 성질로 유한성(finiteness), 명확성(definiteness), 입력(input), 출력(output), 효율성(effectiveness) 등 다섯가지로 서술하기도 한다.

우리 사회에 질서가 없고, 법을 제대로 지키거나 제대로 만들지 않고, 좋은 물건을 만들고도 끝마무리를 못하고, 교육, 금융, 국책 사업과 외교등 각종 정책에서 실수가 일어나는 것도 어떻게 보면 부실한 알고리듬에 기인한다고 볼 수 있다.  간단한 알고리듬을 짜는 훈련을 어려서부터 한다면, 그 훈련은 정직한 생각을 하는 훈련일 것이고, 깊이 있는 생각을 하는 훈련일 것이며, 남을 배려하는 사회를 이루도록 할 것이다.  이것은 바로 수학 교육의 역할이기도 하다.  부실한 알고리듬은 부실한 사회를 야기하고 IMF(Incredibly Miserable Future)를 만나게 한다.  좋은 알고리듬은 좋은 세상을 만든다 [대학신문].

▒▒▒ 좁은 의미의 알고리듬 ▒▒▒

수학자들이 사용하는 좁은 의미의 알고리듬에 대한 정의는 1930년대에 오스트리아의  Kurt G"odel(1906-1978), 영국의 Alan Mathison Turing(1912--1954), 폴란드-미국의 Emil Post(1897--1954), Lambda Calculus 로 유명한 미국의 Alonzo Church(1903--1995), 그의 학생이었고 귀납적(recursive) 함수로 유명한 Stephen Kleene(1909--1994) 등에 의하여 확립되었다.  수학자들은 어떠한 알고리즘이 간단하고, 어떠한 알고리즘이 복잡한가를 이해하기 시작하였다.  그들은 컴퓨터 과학을 탄생시켰으며, 많은 자료에서 원하는 자료를 순식간에 찾아주는 프로그램을 개발하여, 방대한 자료의 인터넷 써치가 가능하도록 하였다.

Turing 은 1930년대에 영국 Cambridge 에 있는 King's college 에 다녔는데, 그때 수리논리학자인 Max Newman 의 강의를 들었다. Newman 은 그 강의에서 Hilbert 가 1904년에 Heidelberg 에서 열린 제3회 국제수학자대회(ICM)에서 제시하고 그 이후로도 이탈리아의 Bologna 에서 열린 제8차 ICM 등에서 계속적으로 강조한 문제 하나를 소개하였다:

Hilbert 의 꿈: 어떠한 수학적 명제라도 그것의 옳고 그름을 판정할 수 있는 효과적인 방법이 있는가?

이와 같이 ``예, 아니오'' 중에서 한가지로 답을 하여야 하는 문제를 판정문제(Entscheidungsproblem, Decision Problem)라고 한다.  국회의원들이 청문회에서 특히 좋아하는 그러한 문제이다: ``본명이 *** 맞습니까? 다른 설명은 필요없으니 `예, 아니오'라고만 답하세요!''  H. Poincar'e 는 Hilbert 의 꿈같은 이야기를 들고는 ``수학적 귀납법을 사용하여 수학적 귀납법을 정당화하려 하지 말라!''는 경고를 하였다 [Poincar'e, 1908].

거짓말장이의 역설 "나는 지금 거짓말을 하고 있다''와 같은 역설이 생기는 이유는, 자신이 기르던 너무나 이성적이어서 굶어 죽은 당나귀로 유명한 프랑스의 Jean Buridan(1295-1360)이 처음으로 명확하게 파악하였듯이, 바로 자신을 언급하는 데 있다 [Podnieks]. 실로 남을 목 졸라 죽이는 살인마도 자신의 목을 졸라 죽이는 것은 불가능할 것이다.  G"odel은 거짓말장이의 역설을 형식언어 체계로 바꾸는 데 성공하였고, 이를 바탕으로  1930년 Hilbert 의 고향인 K"onigsberg 에서 열린 학회에서 Hilbert 의 꿈은 실현할 수 없다는 `불완전성 정리'를 발표하였다:

불완전성 정리: 모순없는 형식 체계는 완전하지 않다.

Turing 은 Hilbert 문제에 깊이 빠져 들었다. 그리고 이 문제의 가장 어려운 부분은 `효과적인 방법'의 의미를 분명히 하는 데 있다는 것을 알았다. Turing 은 달리기를 좋아하였는 데 1936년 어느날 달리기를 하고 나서 쉬다가 Hilbert 문제를 이해하는 방법을 발견하여 현대적인 `계산론'과 `컴퓨터 과학'을 탄생하게 하였다.  이러한 논리적 문제를 이해하고 나서 10여년이 지난 후에야 Turing 과  von Neumann 등의 아이디어를 따르는 현대적인 컴퓨터가 만들어지기 시작하였다. Hilbert 가 말한 `효과적인 방법'의 의미를 현대 수학자들은`좁은 의미의 알고리듬'으로 이해하고 있다.  Turing 은 Hilbert 문제가

정지문제(Halting Problem): 임의의 프로그램과 입력 자료가 주어졌을 때 이들이 유한시간내에 작업을 마치지 않는다는 것을 유한 시간 안에 판정하여 주는 그러한 알고리듬이 있는가?

와 마찬가지라는 것을 보였고, 정지 문제에 대한 부정적인 답을 한 그의 정리가 G"odel 의 불완전성 정리와 동치임을 보였다.

필자는 1970년대에 대학을 다녔는데, 여름방학을 이용하여 한 달 동안 컴퓨터 프로그램과정을 수강한 적이 있다.  서울대학교 공과대학의 첨단 컴퓨터의 용량이 겨우 64KB 이던 그런 시절이었다.  개개인은 프로그램을 펀치카드에 기록하고, 그것에 구멍을 뚫어 컴퓨터에 입력하였다.  컴퓨터 사용자들은 은행에 예치금을 두었고,  컴퓨터를 일정 시간 사용하면, 사용료가 자동으로 은행계좌에서 빠져나갔다.  어떤 날은 소수를 구하는 프로그램을 짜서 제법 방대한 목록을 뽑아 보곤 하였다.  물론 이 때에도 사용료가 예치금에서 빠져 나갔다.  그런데 어느 날은 프로그램에 이상이 있었는지 하루 종일 컴퓨터를 돌리고도 아무런 결과를 얻지 못하였고, 예치금만 몽땅 날린 적이 있었다.  프로그램에 이상이 있을 때  미리 그것을 조사하고 컴퓨터를 돌리는 것을 중지시킬 수 있는 방법이 있었더라면, 아까운 시간과 금전을 날리지 않았을텐데 하는 생각이 들었다.  보편적 이론으로서의 G"odel 과 Turing 의 정리에 의하면 그러한 생각은 실현할 수 없다는 것이다.

앞으로는 `알고리듬'을 좁은 의미로만 사용하고, 그것은 인류가 오랫동안 사용하던 `셈'의 의미를 분명하게 한정하는 Turing 기계를 뜻하며, 컴퓨터 프로그램을 뜻한다.

▒▒▒ Turing 기계 ▒▒▒

Turing 기계란 어떤 물질을 의미하는 것이 아니고 수학적인 개념인 함수의 한가지이다.  배고픈 사람이 음식을 보고 먹을 만큼 먹고는 포만감에 젖어 다른 곳으로 이동하는 것처럼, Turing 기계도 자신의 상태와 입력에 따라 출력하고 상태를 바꾸고 이동한다.  즉, 마음의 상태 집합을 S, 입출력 문자집합을 A 라 하면 Turing 기계는 함수

M :  S × A  →  S × A × {←,→}

를 뜻한다. (엄밀한 정의는 [Cook], [Devlin, 허민], [Lov'asz], [Penrose] 등을 참고할 것.) 이 함수가 바로 알고리듬이요, 프로그램이다.

보기를 들어 기계
 

는 0 또는 1을 입력한 자료에서 1의 개수가 홀수인지 또는 짝수인지를 판정하는 기계이다.

Turing 기계는 자연 언어뿐 아니라 컴퓨터 언어 등을 포함한 넓은 의미의 언어를 이해하는 데 사용되며 이는 1950년대에  A. Chomski(1928- )로 하여금 언어와 문법의 분류를 하는데 결정적인 역할을 한다 [Rosen].
 

▒▒▒ 쉬운 문제와 어려운 문제 ▒▒▒

어떠한 문제가 답을 하기 쉬운 문제이고, 어떠한 문제가 답을 하기 어려운 문제인가? 답을 구하는 데 걸리는 시간이 짧은 문제가 쉬운 문제이고, 그렇지 않은 문제는 어려운 문제이다. 주어진 문제를 푸는 알고리듬---즉, Turing 기계가 얼마나 작동하는가가 시간을 정하는데, 그 시간이 짧다 또는 길다는 것은 개개의 문제마다 의미있는 것은 아니고, 집단문제(mass problem)에 부여된 개념이다.  마치 2 곱하기 3 은 잘 셈하지만, 다른 곱하기는 셈하지 못하는 계산기는 계산기가 아니듯이, 알고리듬이란 특정한 문제만을 푸는 데 사용되는 것이 아니라 보편적인 문제를 해결하여야 한다.

보기를 들어 두 자연수 70 과 1106 의 최대공약수를 구하여 보자. "배우지 못한 사람"은 이 문제를 다음과 같이 풀려고 할 것이다: 우선 70의 약수를 모두 구하고 1106의 약수를 모두 구한 다음 이 두 약수 집합의 공통 부분을 구하고, 그 중에서 가장 큰 것을 답으로 한다.  하지만 유클리드의 호제법을 "배운 사람"은 그렇게 오랜 시간을 써가며 구하지 않아도 된다: 먼저 1106 을 70 으로 나눈 나머지 56 을 얻고 70 을 56 으로 나눈 나머지 14 를 얻은 다음 56 이 14 로 나누어 떨어짐을 알고 14 를 답으로 내 놓는다:

1106 ≡ 56  (mod 70)
70 ≡ 14 (mod 56)
56 ≡ 0 (mod 14).

유클리드 호제법은 특정한 자연수 쌍에만 적용되는 것이 아니라 보편성을 가지고 있어 임의의 자연수 쌍 (m,n) 에 대하여 적용되고, 이때 답을 구하는 데 걸리는 (최악의 경우의) 시간은 입력의 길이에 비례한다: 자연수 쌍 m < n 을 입력하는데 사용되는 비트(bit)수를 가우스 기호 [ ] 를 사용하여 나타내면 [log m + 1] + 1 + [log n + 1] 이고 (이진법을 쓰면 log 의 밑은 2 이고, 십진법을 쓰면 밑은 10, 16 진법을 쓰면 밑은 16 이다), 최악의 경우 하여야 할 나눗셈의 회수는 [1 +  log_{(1+ √ 5)/2} m ] < [1 + 5 log₁₀ m] 이다 (G. Lam'e(1795--1870)의 정리 [Rosen, p.205]).

이와같이 답을 구하기 위하여 시행하는 연산의 수가 입력 길이에 대한 다항식에 지배되는 알고리듬을 다항시간 알고리듬이라 부르고, 다항시간 알고리듬이 존재하는 집단문제---즉, 풀기 쉬운 집단문제 전체집합을

P

로 나타낸다.

정렬문제: 다른 보기로, 1 부터 n 까지의 자연수가 순서없이 한 자씩 적혀 있는 n 장의 카드를 순서대로 정렬하는데 얼마나 시간이 걸리는 지 살펴보자.  특별한 기교를 부리지 않고, 우선 1 이 어디에 있는지 살펴보는데 n 이하의 시간이 걸리고, 그 다음 2 가 어디에 있는지를 살펴 보는데 n-1 이하의 시간이 걸리고, 최악의 경우라도 n(n+1)/2 시간이 주어지면, 카드를 정렬할 수 있다.  그러므로 정렬문제는 쉬운 집단문제이다.  실제로 좋은 알고리듬으로 정렬하면 걸리는 시간은 O(n log n) 정도로 단축할 수 있다.  정렬을 위한 알고리듬은 비단 이러한 카드뿐 아니라, 50명의 수학 답안지를 성적순으로 정렬하여야 하기도 하고, 문서 편집기에서 잘못 사용한 단어를 찾아 고치는 search-replace 기능을 위하여도 필요하고, 도서관의 백만권 자료 중에서 원하는 것을 실시간에 찾고, 전화교환원이 원하는 곳의 전화번호를 재빨리 알려주며, 인터넷을 빠른 시간 안에 뒤지는 것을 가능하게 한다.

쉬운 집단문제의 보기로

• 두 개의 n x n 행렬끼리 곱하기
• 정사각 행렬의 역행렬 구하기
• 두 다항식끼리 곱하기
• 이산 Fourier 변환
• network flow 문제

등을 들 수 있다.

물론 어떤 집단문제가 쉽다는 것은 이론적으로 그렇다는 뜻이지 실질적인 것은 아닐 수 있다.  작년에 어떤 선진국에서 대통령 선거를 마치고는 투표지에 난 구멍의 개수를 잘 세지 못하여 사회적으로 큰 혼란을 일으켰는데, 이와 같이 수학적으로 자명한 문제가 실제로는 아주 어려운 문제일 수도 있다.

다항식 시간 문제와 비다항식 시간 문제에 대한 개념은 von Neumann(1953), Cobham(1964), Edmonds(1965) 등에 의하여 확립되었다 [Cook].

▒▒▒ 어려운 문제 ▒▒▒

물론 모든 집단문제가 다 쉬운 것은 아니다. 어려운 집단문제의 보기로는 하노이 탑 문제라고 부르는 것이 있다. 이 문제는 1883년에 Lucas 라는 오락 수학자가 만든 문제로 다음과 같다.

티벳의 한 고원에 n 층 탑이 있는데,  이 탑의 위치를 다른 곳으로 옮겨야 한다. 이 때 맨 위층부터 차례로 옮겨야 하고, 각 층들을 놓아 둘 수 있는 곳은 현재 자리, 옮길 자리, 여분의 한 자리뿐이다. 그리고 낮은 층을 높은 층 위에 쌓아서는 안된다. 과연 몇번 만에 이 탑을 다 옮길 수 있을까?

n 층 탑을 옮기는 데 걸리는 시간을 T(n) 이라 하면 점화식

T(n) = 2 T(n-1) + 1,    T(1) = 1

을 쉽게 얻고, 따라서 T(n) = 2ⁿ -1 임을 안다.  이 문제는 탑의 층수가 증가함에 따라 해결하는데 걸리는 시간이 기하급수적으로 증가하고, 따라서 어려운 문제이다. 만약 63 빌딩을 1초에 한 층씩 옮긴다면 3천억년 이상이 걸린다.

어떤 집단문제가 쉽다는 것을 보이는 것은 쉽다: 그 집단문제를 해결하는 다항식 알고리듬을 보여주기만 하면 된다.  그러나 어떤 집단문제가 어렵다는 것을 보이는 것은 어려운 일이다. 왜냐하면 어떠한 알고리듬도 쉬운 것이 없다는 것을 증명하는 것이 어렵기 때문이다.

▒▒▒ 풀 수 없는 문제 ▒▒▒

어떤 문제는 너무나 어려워서 풀리지 않는 것도 있다. 대표적인 것이 앞에서 말한 정지 문제이다. 다른 보기로는

타일링 문제: 임의의 다각형 집합이 평면 타일링을 하는가를 판정하는 문제

를 들 수 있다 [Berger], [Croft et al.], [Gardner], [Lov'asz], [Penrose]. 다각형의 종류가 불가산수이기 때문에 가산수의 기계들로 해결할 수 없는 것은 당연하다. 그러나 다각형을 "동서남북 각변에 색을 칠한 정사각형" 또는 "폴리요미노"로 한정하더라도 판정불가능하다.

판정 문제 중에서 가장 유명한 것 중의 하나가 Hilbert 의 열번째 문제라고 부르는 Diophantus 방정식에 관한 것이다:

Hilbert 의 열번째 문제: 일반 정수방정식 p(x₁, ... , x_n) = 0 이 정수해를 가지는 지를 판정할 수 있는 알고리듬이 존재하는가?

1970년에 Matiyahsevich 는 이 문제에 대한 부정적인 답을 하였다. 또 다른 보기로는 1914년 A. Thue 가 질문한

단어 문제(word problem): 일반 자유군의 원소 a₀, a₁, ... , a_n 에 대하여 a₀ 은 a₁, ... , a_n 이 생성하는 부분군의 원소인가?

이다. 이 문제도  1947년에 E. Post 와 A. Markov 에 의하여 판정 불가능하다는 것이 밝혀졌다 .

▒▒▒ 수학자들은 해결사 ▒▒▒

20세기 수학의 주요한 특징은 "존재성과 유일성"에 관한 이해가 주를 이루었다.  공간이나 구조에 대한 명확한 개념과 용어 및 방법들이 정립되지 않은 시절이었다.  그러나 21세기가 가까워 지면서 수학자들은 "존재성과 유일성" 문제를 상당히 잘 이해하게 되었고, 어떤 것은 그들의 상식이 되었다.  그 대신 ``어떻게 찾을 것인가?''하는 문제는 여전히 풀리지 않은 것들이 많이 있고, 큰 관심을 끌고 있다.

어려운 문제에 부딪히면 그 난관을 극복하는 법이 있는가? 얼마나 많이 있는가? 이러한 것들이 20세기 수학자들이 많이 연구한 것이라면, 21세기 수학자들은 난관을 어떻게 구체적으로 극복할 것인가? 하는 문제를 더 많이 연구할 것이다.

수학자들은 문제가 주어지면

• 답이 존재하는가?
• 답을 어떻게 찾는가?
• 찾은 것이 바른지를 어떻게 검증하는가?

등을 연구하여 왔고, 이것은 마치 사건이 생겼을 때 해결책을 구하는 자세와 같다.  그런 의미에서 수학자들은 해결사라 말할 수 있다.

▒▒▒ NP - 아리송한(Hard) 문제 ▒▒▒

어떤 집단문제들은 어려워 보이기는 하지만, 그 답을 보면 옳다는 것을 검증하기가 쉬운 그러한 집단문제들이 있다. 마치 평범한 고등학생들이 ``수학의 정석''과 낑낑대고 씨름하다가 포기하고는 해답을 보고 나서 "아! 바로 그것이구나" 하듯이. 이러한 집단문제---미정다항시간집단문제(nondeterministic polynomial time problem)들의 집합을

NP

라 한다. 이러한 이름이 붙은 이유는 다음과 같다. 앞에서 Turing 기계를 설명하였는데, 이것은 함수이고, 따라서 결정적인(deterministic) 행동을 하는 기계이다. 집합론적 입장에서는 함수란 관계의 일종이다. Turing 기계에서 함수를 관계

M  ⊂  S × A × S × A × {←,→}

로 바꾸기만 하면 미정적인 Turing 기계가 된다.  그러므로 미정적인 기계에서는 입력을 보고 그 다음 상태와 출력 및 움직이는 방향이 한가지로 정해지는 것이 아니고, 여러가지로 나타난다. 이러한 미정적인 기계를 이용하여 다항식 시간안에 답을 구하는 알고리듬이 있는 문제가 바로 NP 에 속하는 문제이다. 이 정의는 ``쉽게 검증할 수 있는 증명서(certificate)를 가진 문제''로 정의하는 것과 동치임이 알려져 있다.  현재 인류가 사용하고 있는 컴퓨터는 모두 결정적인 Turing 기계이고, 미정적인 기계는 아직 이용되고 있지 않다.  확률론적인 기계나 양자 기계 등이 연구되고 있기는 하지만 실용 단계는 아니다.  집단문제중에는  하노이의 탑처럼 NP 에 속하지 않는 문제도 많이 있다.  물론 P 가 NP 의 부분집합이기는 하지만, NP 가 P 와 다르다는 것이 증명된 것은 아니다.  Clay 수학연구소에서 현상금을 건 문제가 바로 "P = NP ?"이다.  이 문제는 "P ≠ NP ?" 와 마찬가지이다. 한 은사님께서 말씀하시기를 "의문문은 긍정문으로 하거나 부정문으로 하더라도 그 뜻은 마찬가지이다"라고 하셨는데, 페티김의 "누가 그사람을 모르시나요?"와 조성모의 "아시나요?"를 들어 보면 둘 다 "이별의 슬픔"을 노래한 것임을 알 수 있다.   이제 NP 에 속하는 문제들의 보기를 몇가지 든다.

TSP 문제: 만득이가 방학을 이용하여 배낭 메고 세계 여행을 떠난다고 하자. 방문하고 싶은 도시는 런던, 파리, 베를린, 로마, 그라나다, 이스탄불, 모스코바, 페이킹, 뉴욕, 토교 등 모두 열 곳. 여행사에 전화하여 어떤 방법으로 도시들을 방문하는 것이 비행기 삯을 가장 저렴하게 하는지를 알아 본다.  물론 서울에서 출발하여 서울로 돌아와야 하니까 여행사 직원이 조사하여야 할 경우의 수는 모두 10! = 3628800.  그러나 만득이는 여행사 직원이 추천한 방법을 그 자리에서 따르지 않고, 몇군데 다른 여행사에 더 문의한다. 만득이가 풀려고 하는 문제는, 부인의 허락이 없어 외박하지 못하고 하루 종일 여러 도시를 돌아 다니다가 지친 육신을 이끌고 집으로 다시 돌아오는 외판원 문제(TSP, Traveling Salesman Problem)와 마찬가지다.  만득이 문제는 여행사 직원이 어리석어서 풀기 어려운 것이 아니고, 문제의 속성이 그러하기 때문이다.  핀볼 게임기를 만들려면 수많은 못을 박고 나사를 조아야 하는 데, 작업 시간을 줄일 수 있는 방법을 아는 것은 중요한 일이다. 컴퓨터 칩이나 전자회로판을 설계할 때 레이저 드릴로 65,000 개 이상의 구멍을 내야 하는 경우를 생각해 보면 좋은 알고리듬의 중요성을 실감하게 된다

그래프에 관한 Hamilton 회로 문제: 사원수의 발견으로 유명한 W. Hamilton(1805-1865)은 1857년에 "20면체 게임"을 발명하여 게임 판매 업자에게 25 파운드에 팔았다. 업자들은 이 게임을 `세계 여행(A Voyage Round the World)'이라는 이름으로 판매하였는 데,  20면체의 모서리를 따라서 모든 꼭지점을 오직 한번씩 지나 다시 처음 꼭지점으로 되돌아 오는 그러한 놀이였다.  이 게임이 잘 팔리지 않아 업자는 투자를 잘못한 것이 되었지만, 그 후로 그래프에서 모든 꼭지점을 오직 한번씩  지나고 처음으로 되돌아 오는 경로를 Hamilton 회로라고 부른다.  Hamilton 회로 문제는 NP 에 속하는 문제이다.  그러나 한붓 그리기 문제(그래프의 모든 모서리를 오직 한번씩 지나는 문제)는 아이들을 돌보던 L. Euler 가 아주 쉬운 문제로 만들었다.

시간표 짜기: 요즈음 대학의 시간표---즉, 수강편람을 보면 한심하기 짝이 없다.  학생수는 20년전보다 2배로 늘었는데, 대학을 운영하는 알고리듬은 갈수록 엉망이다.  부전공제도다, 복수전공제도다, 조기졸업이다, 대학원 중심이고, 학부 변두리다 어쩌구 저쩌구 하지만 수강편람을 보면 도저히 학생들에게 양질의 교육을 제공한다고 보기 힘들다.  어떤 시간은 학교 저 구석 건물의 4층에서 강의가 있고, 그 다음 시간은 반대쪽 건물의 4층에서 강의가 있다.  기말고사를 볼 때에도 같은 날에 두가지 시험을 치르지 않도록 시간표를 짜면 좋을텐데.  이러한 문제는 학교 행정직원들의 무책임한 자세 때문인 것이 대부분이지만, 한편으로는 이 문제가 본질적으로 가지고 있는 속성때문이다.

퍼즐맞추기: 빈치 마을의 레오나르도가 그린 모나리자를 500조각낸 퍼즐을 구입하고는 밤을 새워가며 짝을 맞추느라고 고생한 적이 있다.  문제를 푸는 것은 어렵지만(500! ≒ 1.2 × 10¹¹³⁴), 답을 보고는 그것이 옳다는 것을 판정하는 데는 500개 조각만 조사하면 된다.

소수판정: 자연수 중에서 약수의 개수가 두개인 자연수를 소수라 한다.  1보다 큰 자연수는 더 이상 쪼개지지 않는 소수이거나 또는 소수들의 곱으로 표현되는 합성수이다.   소수의 개수가 무한하다는 것은 유클리드 시절에 이미 알려졌지만, 주어진 큰 수가 소수인지를 판정하는 것은 여간 어렵지 않다.  평범한 방법으로 자연수 n 이 소수인지 판정하려면, 최악의 경우, √n 이하의 모든 자연수로 나누어 보아야 한다. 이때 걸리는 계산의 시간은 입력한 비트수 b = [1+ log n] 에 대한 지수함수로 나타난다.  그러므로 이러한 (원시적인) 방법은 소수판정문제가 어렵다는 것을 암시하여 준다.  그러나

Fermat 의 작은 정리:   p 가 소수이면 임의의 자연수 a 에 대하여 a^p ≡ a (mod p) 이다.

를 이용하여 1975년에 V. Pratt 는 모든 소수에는 증명서가 있어서 이것을 보면 쉽게 그 수가  소수임을 알 수 있다는 것을 보였다. 따라서 소수판정문제는 NP 에 속한다.   `소수문제는 P 에 속할 것이다'라고 생각하는 학자들이 있지만 아직 증명을 가지고 있는 것은 아니다.

합성수판정:   명제 "4,003,997 는 합성수이다"가 참이라는 것을 확신하려면 제법 생각하여야 한다.  하지만 이 수가 1999 과 2003 의 곱이라는 것을 보이는 것은 쉽다:

1999 ×2003 = (2000 -1) ×(2000 + 3) = 4,000,000 + 4,000 - 3 = 4,003,997

수학자들은 "소인수 분해가 어렵다"는 것에 대한 보편적인 증명이 나오기 전까지는 그것이 옳다고 말하지 않는다.

이삿짐짜기:  어느날 컴퓨터 파일 다섯 개

filenameA (300 kb), filenameB (400 kb), filenameC (600 kb), filenameD (700 kb), filenameE (800 kb)

를 장당 용량이 1440 kb 인 3.5인치 플로피 디스켓 두장에 담으려고 복사 명령을 하였더니, filenameA, filenameB, filenameC 를 첫장에 복사하고, filenameD 는 복사하다가 중간에 포기하고 `용량이 부족하니 다른 디스켓을 넣고 Any Key 를 누르시오'라고 하였다.  그래서 두 번째 디스켓을 넣었더니, 드라이브가 망가졌다.  처음 디스켓을 빼지 않았기 때문이다.  급히 드라이브를 수리한 다음, 다시 복사 명령을 하였더니 아까와 같은 지침이 내려왔다.  이번에는 첫 번째 디스켓을 빼고 두 번째 디스켓을 넣은 다음 `Any Key'를 열심히 자판에서 찾았지만 보이지 않았다. 그래서 자판을 만든 회사에 `왜 당신회사 자판에는 Any  Key 가 없느냐?'고 문의하였더니 `Enter'나 `Shift' 등을 포함한 모든 키가 Any Key 라 하였다. 성공적으로 Any Key 를 눌렀더니 filenameD 가 복사되었고, 계속하여 filenameE 를 복사하다가 중간에 포기하고는 또 다시 `용량이 부족하니 다른 디스켓을 넣고 Any Key 를 누르시오'라는 지침이 내려았다. 내가 가진 플로피 디스켓은 두장뿐인데.

복사 알고리듬은 각 파일을 복사하기 전에 디스켓에 용량이 충분한지를 먼저 조사하여야 하고, 그런 다음에도 filenameA, filenameB, filenameC 를 첫 번째 디스켓에 넣을 것이 아니라 filenameA, filenameB, filenameD 를 첫 번째 디스켓에, filenameC, filenameE 를 두 번째 디스켓에 넣어 임무를 성공적으로 완수하였어야 하였다.

비슷한 문제로, 살기 좋은 나라를 만들기 위해 수도를 다른 도시로 옮기는 문제를 생각하자. 이때, 많은 짐들을 트럭 1000대에 다 실으려면 어떠한 순서로 짐을 실어야 할까? 이와 같은 최적화 문제가 안고 있는 난이도도 NP 이다.

선형계획법: 선형방정식의 연립 부등식을 푸는 문제는 군수 산업이나 산업 공학에서도 아주 중요한 문제이다. 이 문제를 단체법(simplex method)으로 많이 풀고 있지만 그 알고리듬은 지수시간 알고리듬이다. L. Khachian 은 1979년에 다항시간 알고리듬을 개발하였고, 그 이후로도 좋은 알고리듬이 많이 개발되었다.   그러므로 선형계획법은 P 에 속하는 문제이다.  하지만 실수해가 아니고 정수해를 구하는 문제라면 NP 에 속한다.

▒▒▒ SAT 문제 ▒▒▒

승용차를 타 본 사람이면 실내등이 언제 켜지는지를 잘 안다: 차문이 하나라도 열려 있으면 켜지고, 모두 닫혀 있으면 꺼진다. 이처럼 전등 하나가 여러가지 스위치와 복잡하게 연결되어 있는 전기 회로의 설계도면을 보고  어느 스위치들을 올리고 어느 스위치를 내리면 불이 들어올까를 판정하는 문제가 바로 SAT 문제(satisfiablity problem)이다.

영국의 G. Boole(1815--1864)은 1848년에 기호 논리학에 관한 책 `The Mathematical Analysis of Logic'을 출판하였고, 1854년에는 유명한 `The Laws of Thought'를 출판하였다. 이 책에는 명제로부터 새로운 명제를 얻는 방법

 p,     NOT p,     p AND q,     p OR q

등이 적혀 있고, 현재 불 대수(Boolean Algebra)라고 부르는 개념을 확립하였다. 다음 그림들은 이변수 불 함수 열여섯가지 모두를 나타낸 것이다.

Boole 의 논리는 1938년 C. Shannon(1916- )의 연구로 전기회로에서 스위치를 올리고(TURE) 내리는(FALSE) 것에 이용되어 20세기의 디지털 혁명이 일어나는 정신적 바탕이 되었으며, 정보이론(IT, Information Theory)이나 인공지능(AI, Artificial Intellligence)뿐 아니라 러시아의 A. Kolmogorov 나 미국 IBM 회사의 G. Chaitin 등에 의한 AIT(Algorithmic Information Theory)가 발전하는 데도 커다란 영향을 끼쳤다 [Casti, 2000].

▒▒▒ NP-완비(Complete)문제 ▒▒▒

얼마전에 큰 행렬들의 곱하기를 아주 빨리 하는 MaTricks 라는 프로그램을 하나 구입하여 집에 와 설치하고 사용법을 적은 설명서를 읽어 보았더니 마지막에 깨알 같은 글씨로 "본 제품은 크기가 10×10 이하인 행렬에만 사용할 수 있습니다"라고 적혀 있었다.  이 프로그램을 사용하여 두개의 20×20 행렬을 곱한 것을 구하려 하였지만, 크게 실망하지는 않았다.  왜냐하면 20×20 행렬은 네 개의 10×10 행렬로 쪼갤 수 있고, 따라서 MaTricks 를 이용할 수 있기 때문이었다. 이와 같이 어떤 문제를 다항 시간안에 P 문제로 변형할 수 있다면 처음 문제 역시 P 이고, 다항 시간안에 NP 문제로 변형할 수 있다면 처음 문제 역시 NP 이다.

어떤 NP 문제 T 가 임의의 NP 문제를 다항시간안에 T 로 바꾸어 해결할 수 있다면 그 문제를 NP-완비라 부른다.  NP-완비 문제는 NP 문제 중에서 가장 어려운 문제라 할 수 있다. 이러한 문제가 존재하는 지도 분명하지 않다. 1971년에 Stephen Cook 는 NP-완비 문제라는 개념을 확립하고 SAT 문제가 NP-완비라는 것을 증명하였다.   그러므로  NP 와 P 가 같다는 것을 보이기 위해서는 모든 NP 문제가 다 P 에 속한다는 것을 보일 필요가 없고, 한가지 NP-완비 문제가 P 에 속한다는 것을 보이면 된다. 물론 NP 와 P 가 다르다는 것을 보이기 위해서는 P 에 속하지 않는 NP 문제를 하나 발견하면 된다.

물론 지뢰밭의 크기는 한정된 것이 아니다.  Kaye 는 전기회로를 다항식 시간내에 지뢰밭으로 변형하는 방법을 보여 지뢰밭에 주어진 정보가 모순이 없다는 것을 판정하는 문제가 SAT 문제와 동치임을 보였다.  지뢰 찾기 문제 외에도 바둑이나 장기, 소코반 등 여러 게임들의 난이도에 대하여 연구하는 학자들이 많이 있다.

▒▒▒ 두가지 미래 ▒▒▒

많은 학자들은 P ≠ NP 라고 믿고 있다.  만약 이것이 밝혀지면, 현재 전자상거래 등에서 많이 사용하는 RSA(R. Rivest, A. Shamir, L. Adleman) 암호 체계 같은 것이 상당히 안정적이라는 것에 대한 이론적 배경을 제공하는 셈이 된다.  하지만 누군가가 P = NP 를 증명한다면 현재 사용하는 암호체계의 신빙성에 큰 타격을 주게 된다.  아마 P = NP 를 증명한 사람은 Clay 수학연구소에 연락하는 대신 다른 곳에 투자하면 더 큰 보상을 받을 수 있을 것이다. 하지만 이 경우는 어렵게 보이는 문제에 대한 쉬운 알고리듬을 발견한 것이 되어 실생활에 큰 발전을 줄 것이다.  대학 행정직원들도 수강편람을 잘못 짜면 그 책임을 면하지 못할 것이고, 국제 어업협정을 하며 쌍끌이 어선을 빼 먹거나 인공호수나 고속전철 등 국책 사업을 잘못 정한 이들도 갈 곳은 정해지게 된다.

2002년 7월 추가: 어쩌면 세 번째 미래가 있어  "P = NP" 와 "P ≠ NP"를 모두 증명할 수 없다는 것을 증명할 지도 모른다.

▒▒▒ 감사의 글 ▒▒▒

이 글을 쓰는 동안 쾌적한 환경을 마련해 준 서울대학교와 고등과학원에 감사드린다.  그리고 대한수학회 소식지 편집자의 의욕에 찬 활동에 조금이나마 도움이 되었으면 좋겠다.

▒▒▒ 참고문헌 ▒▒▒

과학동아, 12억원 상금 걸린 지뢰찾기게임, 2001년 1월호, 130-131.

대학신문, 과학에세이 "알고리듬이 만드는 좋은 세상", 서울대학교 2000년 9월 18일.

신현식외 15인, 이산수학, 교학사, 1994.

R. Berger, The undecidability of the domino problem, Memoirs Amer. Math. Soc. 66 (1966).

J. Casti, Five Golden Rules, John Wiley & Sons, Inc., 1996. 한태식, 권기호, 김정헌 옮김, ``20세기 수학의 다섯가지 황금율'' 경문사, 1999.

________, Five MORE Golden Rules, John Wiley & Sons, Inc., 2000.

B. Cipra, What's happening in the Mathematical Sciences, I , II (ch. 6, ch. 9). Amer. Math. Soc., 1993, 1994. (김재겸, 김한두 공역, 교우사, 1996)

S. Cook, The P versus NP Problem,  http://www.claymath.org/prize_problems/p_vs_np.pdf

H. Croft, K. Falconer, R. Guy, Unsolved Problems in Geometry, Springer, 1991.

D. Dennett, Darwin's dangerous idea : Evolution and the meanings of life, Simon & Schuster, 1995.

K. Devlin, Mathematics: The New Golden Age, Penguin Group Ltd., 1988. 허민 옮김, 수학: 새로운 황금시대, 경문사, 1995, 1999.

R. Feynmann, Lectures on Computation, Addison Wesley, 1996.

M. Gardner, Scientific American, Jan. 1977, 110--121.

R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley Publ. Co., 1989.

P. Hoffman, Archimedes' Revenge, Fawsett Crest, New York, 1988.

D. Hoffstadter, G"odel, Ecsher, Bach: an Eternal Golden Braid, Basic Books, Inc., 1979. 박여성 옮김, 괴델, 에셔, 바흐, 까치, 1999.

V. Klee, S. Wagon, Unsolved Problems, Math. Assoc. Amer., 1991.

D. Knuth, Fundamental Algorithm, The Art of Computer Programming, Addison-Wesley, 1968, 1973.

L. Lov'asz, Computation Complexity, Lecture Notes.

R. Penrose, The Emperor's New Mind: concerning computers, minds, and the laws of physics, Oxford Univ. Press, 1989. 박승수 옮김. 상,하. 황제의 새 마음 : 컴퓨터, 마음, 물리법칙에 관하여,  내일을 여는 책,  서울, 이화여자대학교 출판부, 1996.

__________, Shadows of the Mind: An Approach to the Missing Science of the Consciousness, Oxford Univ. Press, 1994.

R. Penrose, A. Shimony, N. Cartwright, S. Hawking, The Large, the Small and the Human Mind, Cambridge Univ. Press, 1997.

I. Peterson, A Mathematical Mystery Cruise, W. H. Freeman & Co., 1988.

K. Podnieks, Around G"odel's Theorem, http://www.ltn.lv/~podnieks/

H. Poincar'e, Science et methode, Paris, 1908.

V. Pratt, Every prime has a sufficient certificate, SIAM J. Comput. 4 (1975), 214--220.

K. Rosen, Discrete Mathematics and its applications, McGraw-Hill, Inc., 1988, 1995.

S. Smale, Mathematical Problems for the next century, Math. Intelligencer 20 no.2 (1998), 7--15.

I. Stewart, Million Dollar Minesweeper, http://www.claymath.org/prize_problems/million-dollar-minesweeper.htm

A. Turing, Computing Machinery and Intelligence, Mind, 1950.

H. Wilf, Algorithms and Complexity,  Internet Edition, 1994. (http://www.cis.upenn.edu/~wilf/AlgComp2.html)

많은 경우의 최적화 방법 연구는 해결하고자 하는 문제마다 각기 다른 그 특성에 맞추어 개발해야 하는 어려움이 있다.

이에 따라 특정 문제가 갖는 정보에 크게 구속되지 않고 다양한 문제에 적용 가능한 상위 수준의 방법인 메타 휴리스틱스(Metaheuristics)에 대한 이론과 그 응용에 관한 연구가 진행되었다. 대표적인 메타 휴리스틱스로는 유전적 알고리즘, 시뮬레이티드 어닐링, 타부 탐색 등이 있다.

메타 휴리스틱스(Metaheuristics)란 알고리즘에 대한 다른 표현으로 특정 계산 문제에 의존하지 않는 휴리스틱스를 말한다.

즉 특정 문제에 한정되지 않고 어떠한 문제에 대해서도 범용적으로 대응할 수 있도록 설계된 알고리즘의 기본적 뼈대를 의미한다.

메타 휴리스틱스는 모델링, 시뮬레이션 기술과의 결합을 전제로 한 최적화 수법의 개발과 최적화 수법과의 결합을 전제로 한 모델링, 시뮬레이션 기술 개발에 의한 최적화 기술의 발전적 재구축을 위한 주요 기술이 될 것이다. 그리고 이러한 최적화의 뼈대가 실용적인 레벨에서 실현되면 여러 분야에 대한 최적화의 보급을 촉진할 수 있을 것이다.

조합최적화 문제와 지역탐색

1. 조합최적화 문제

S는 주어진 제약조건에 맞는 이산적인 집합(=해집합)

x는 가능해(feasible solution)    

⇒ 이 문제는 대부분 NP-hard로 Heuristic 접근 방법이 필요

• Constructive

• Local search(지역탐색) : 근방(neighborhood)의 설정,

• 교환알고리즘: 스케줄링(1965), 그래프 분할(Kernigan&Lin, 1970), TSP(L&K, 1973)

예1) GPP(Graph Partitioning Problem)

그래프 G(V,E)가 주어졌을 때 vertex의 집합 V를 동일한 개수의 원소를 갖도록 두 개의 집합 V1과 V2로 나눌 때, V1과 V2를 가로지르는 edge의 수(또는 가중치의 합)를 최소로 만드는 방법을 찾는 문제

- 비용함수:

- 근방: 가능해의 k-교환(exchange) 근방

- k개의 vertex쌍 을 선택하여 각각을 교환

예2) TSP(Traveling Salesman Problem)

n개의 도시가 주어지고 i, j 도시 사이의 거리가 행렬()로 주어졌을 때 출발 도시에서 가장 최소의 거리로 모든 도시를 한 번씩 거쳐서 다시 출발 도시로 돌아오는 경로(tour)를 찾는 문제

- 해: (는 도시 다음에 방문되는 도시)

- 비용함수:

- 근방: (k-exchange 근방)

Hamiltonian Cycle(or Tour)에서 edge k개를 대체

지역 최적이 전체 최적해가 되려면

3. 근방의 설정

a) k-exchange 근방: k가 크면 근방이 복잡(), 지역해는 좋아짐

b) 변동길이 근방: GPP에 대한 K-L algorithm, 1970

a, b 교환의 이득: (현재 일 때)

[STEP 1] g(a,b)가 최대가 되는 쌍을 선택(음수라도 무관)

[STEP 2] 선택된 쌍을 잠정적으로 교환

[STEP 3] STEP1, 2를 n회 반복하여 를 계산(먼저 고려된 쌍은 제외)

[STEP 4] 를 계산

[STEP 5] 가 최대가 되는 k 선택. 이 때 이면 이웃해로 채택하고 과정반복, 아니면 stop

c) 기타 수정법: GPP에서 2-exchange를 2번의 1-exchange로 하는 방법 등

4. 지역 탐색법에서 최적(에 가까운) 해를 얻는 방안

a) 초기해를 달리하여 여러 번의 지역 탐색을 시도

- 소모된 시간에 대한 알고리즘의 효율성이 문제

- 초기해(가능해)를 만들어 내기도 쉽지 않음

b) 해집합의 보다 많은 부분을 탐색할 수 있도록 근방의 구조를 바꿈

- 문제의 특수성에 따라 적절한 근방 구조를 찾기가 힘들다

c) 지역 탐색법을 수정하여 비용이 증가하는 이동도 제한적으로 허용

- 비용 증가의 이동을 어떤 방식으로 허용하는가?

5. Metaheuristics의 등장

1975: GA(Holland) → EC(Evolutionary Computation)

1983: SA(Kirpatrick et al.)

1987: TS(Glover)

1991: Ant System(Colorni, Dorigo, Maniezzo) → ACO(Ant Colony Optimization) 등