The Millennium Problems: The Seven Greatest Unsolved

수학의 밀레니엄 문제들 7
케이스 데블린 지음, 전대호 옮김 / 까치 / 2004년 2월

수학의 밀레니엄 문제들 7 | 원제 The Millennium Problems: The Seven Greatest Unsolved

케이스 데블린 (지은이), 전대호 (옮긴이)

Mathematical Puzzles of Our Time (2002)
출간일 : 2004-02-29 | ISBN : 8972913707

차례

0. 도전장은 날아왔다
1. 소수들의 노래: 리만가설
2. 우리 자신을 이루는 장들: 양 - 밀스 이론과 질량 간극 가설
3. 컴퓨터가 힘을 쓰지 못할 때: P 대 NP 문제
4. 물결을 일으키며: 내비어 - 스톡스 방정식
5. 부드러운 행동의 수학: 푸앵카레 추측
6. 방정식을 풀 수 없을 때를 알기: 버치와 스위너톤 - 다이어 축측
7. 그림 없는 기하학: 호지 추측

[The Millennium Problems: The Seven Greatest Unsolved]는 힐베르트가 제시한 23개의 문제가 [리만 가설]을 제외하고 모두 풀린 후, 그렇다면 새로운 밀레니엄을 맞아 현재 수학은 어떤 문제를 가지고 있고 어떤 방향으로 나아가야 하는가를 두고 고심한 끝에 클레이 수학 연구소(CMI)가 각 문제당 100만 달러의 현상금을 걸고 발표한 7개의 수학 문제들을 다루고 있는 책입니다. 7개의 수학이 다루고 있는 범위는 꽤 넓어서, 물리학쪽에서 쓰이는 응용수학에서부터 위상학에 이르기까지 폭넓게 걸쳐 있습니다.

일반적인 기준으로 볼 때 이 책은 일전의 [Elegant Universe]와 같은 카테고리 - 이른바 교양과학서적 정도 - 로 묶기에 전혀 문제가 없어 보입니다. 제목에서부터 풍기는 분위기, 그리고 차례에서 볼 수 있는 내용에 대한 추측으로 보아도 그렇습니다. 그런데, [Elegant Universe]와 이 책은 많이 다릅니다. 기본적으로 주제에 접근하는 방식이 매우 다르기 때문입니다.

일반적인 상식이나 직관으로 간단하게 이해하기란 무지막지하게 어려운 [Superstring theory]를 설명하기 위해 Brian Greene이 선택한 방법은 일종의 정공법이었습니다. 물론 책의 두께를 10배 이상은 가뿐하게 늘려버릴 수 있는 수식같은 것은 아예 제외한다는 엄청난 시도를 하기는 했지만, 그래도 책은 [Superstring theory]의 탄생 이전부터 현재에 이르기까지 알아야 할 모든 것을 어떻게든 풀어서 설명하려는 시도를 하고 있습니다.

그러나 이 책, [수학의...]에서 저자가 선택한 방법은 일종의 우회로입니다. 각 문제들에 대해 직접적으로 파고들기보다는 그러한 문제가 발생한 배경과, 그 문제를 포함하는 수학 분류에 대한 설명을 통해 문제를 간접적으로 이해할 수 있게 하고자 하고 있습니다.

이러한 방식을 선택한 이유가 있기는 합니다만, 이 방식이 효과적이지는 않습니다. 몇몇 문제 - 상대적으로 이해하기 쉽다고 여겨지는('풀기 쉬운'이 아닙니다!) - 들의 경우에는 잘 먹혀 들어가지만, 저자 스스로도 이해하는 데 꽤 공을 들였다고 말하고 있는 후반부의 호지 추측과 같은 문제를 읽어 보면 결국 책 안에서 문제를 모두 이해할 수 있는 실마리를 제공하지 못한다는 사실을 알게 됩니다.

이유는 크게 두 가지입니다. 먼저 문제 자체의 난이도가, 비교적 얇은 책 한 권으로 설명하기에는 지나치게 어렵다는 점입니다. 단순하게 [문제가 어렵다]고 하기 보다는, 문제를 이해할 만한 기본 상식을 쌓는 것이 어렵다고 이야기해야 더 맞는 말이겠습니다. 수학의 각종 분야들은 그야말로 고도의 추상화가 이루어져 있고, 이 문제들의 대부분은 그러한 추상화의 최상위에 위치하고 있는 경우가 대부분이기 때문입니다. 직관으로 이루어지는 명확한 이해를 기반으로 추상화를 시작하여 문제를 이해할 만한 추상화를 이루어내는데 필요한 설명만으로도 이미 [일반인을 위한]이라는 딱지는 붙이기도 어려울 정도가 되고, 분량도 각 문제당 책 한권 이상을 필요로 할 것임을 말할 나위도 없을 정도입니다.  

다음의 이유로는, 이 책은 어디까지나 [문제에 대한 간단한 소개]를 목적으로 한 책이지 [완전하고 정확한 문제의 설명]을 목표로 한 책이 아니기 때문입니다. 이 문제들을 선정하고 문제당 100만 달러의 상금을 건 클레이 수학 연구소(CMI)에서는 문제에 직접 도전할 사람들을 위해 문제에 대한 상세 설명과 제한 조건등을 포함한 [정확한 문제의 설명]을 출간 및 홈페이지에 게재한 바가 있습니다. 즉, 이 책은 이러한 설명으로는 문제를 쉽게 이해하지 못하는 일반인들을 위해 이런 문제가 있고 대충 이러이러한 내용이다-라고 간략하게 설명하는 일종의 개요 정도의 역할을 하는 셈입니다.

위의 단점들을 제하고 본다면 꽤 나쁘지 않은 책입니다. 모든 문제가 다 호기심을 불러 일으키지는 않을 것이라는 생각을 해 본다면 마음에 드는 몇몇 문제만 선별하여 읽어보는 것도 괜찮으리라는 생각을 합니다. 저자는 난이도 순으로 문제를 배열하였다고 밝히고 있고, 읽어본 느낌으로도 실제 그런 배열을 가지고 있어서 앞부분은 비교적 쉽게 문제의 핵심을 이해할 수 있지만 후반부에 가면 문제를 이해하기는 커녕 문제의 배경조차 이해하기가 힘든 경우도 있습니다. 개인적으로는 리만 가설/P vs NP/푸앵카레 추측 정도가 비교적 큰 무리없이 즐겁게 읽을만 한 부분이라고 생각합니다. [Elegant Universe]보다 이해하기에 조금 더 난이도가 높아서, 기본적인 수학 상식을 가지고 있거나 책을 읽다가 모르는 부분은 찾아보는 정도의 노력은 기울이는 편이 좋습니다.

p.s : 덧붙여서, 비교적 [이해하기 쉬운] 한 문제 정도를 간단하게 적어보려고 합니다. 책의 내용에 관심이 있으시다면 읽어보셔도 좋고, 그렇지 않다면 읽지 않고 넘겨 버리셔도 좋겠습니다. 3번 문제인 P vs NP 문제입니다.

P vs NP 문제는 [계산 가능성]에 대한 탐구입니다. 조금 더 정확하게 이야기하자면, 특정 문제를 컴퓨터를 이용해 얼마나 효율적으로 해결할 수 있는가, 에 관한 이야기라고 보시면 되겠습니다.

약간은 전공쪽에 가까운 이야기가 되어버립니다만, 계산 단계를 결정하는 방법이 있습니다. 간단하게 예를 들자면, 특정 수식을 컴퓨터로 계산하는데 걸리는 시간은 얼마인가? 라고 물었을 때를 가정해 봅시다. 여기서 계산에 걸리는 시간이란 자료의 양에 따르는 비율적인 시간 증가분이므로, 실제 계산 속도는 무시하고 계산에 얼마나 많은 단계들이 필요한가를 세는 것으로도 충분해집니다.

이런 경우 N자리 수 둘을 곱하는데 필요한 단계는 N^2개의 기초 정수쌍 곱셈에, 올림을 감안한 N개의 덧셈을 합쳐 N^2+N의 단계가 필요하게 됩니다.(이 과정을 진지하게 이해할 필요는 없습니다) 이 때 언제나 N^2+N < N^2+N^2 이므로, 근사적으로 N자리 수 둘을 곱하는데는 언제나 2N^2보다 적게 시간이 걸린다고 이야기할 수 있게 됩니다.

이러한 기초 단계들을 분류하는 기준이 생기게 되는데, 시간이 적게 걸리는 순서대로 배열하면 다음과 같습니다.
선형 시간 : 덧셈과 같이 선형으로 계산 시간이 증가하는 경우
제곱 시간 : 곱셈과 같이 크기 N인 경우 C*N^2의 시간이 필요한 경우
다항 시간 : C*N^k의 시간이 필요한 경우
여기서 다항 시간이 걸리는 문제들이 Polynomial-time Process, 즉 P 문제가 됩니다.
그리고 마지막으로 지수 시간 문제는 2^N 이상의 시간이 걸리는 문제가 됩니다.

쉽게 생각할 수 있는 것이겠지만 P 문제의 경우 N이 어느 정도로 커져도 계산에는 전혀 문제가 되지 않습니다. 즉, [컴퓨터를 이용해 효율적으로 계산할 수 있는] 범주에 들어가는 계산 과정입니다. (N^3와 같은 문제에서 N이 50일 경우 0.2초 이내) 반대로 지수 시간 문제의 경우 2^N만 해도 N이 50일 경우 35년 이상이 걸리는, P 문제와 반대로 컴퓨터로 효율적으로 해결할 수 없는 문제입니다.

여기서 진짜 문제는 시작됩니다. P형과 지수 시간 형의 중간에 있는 몇몇 특이한 형태의 문제들 - NP형이라고 부르는 - 은 과연 P문제처럼 효율적으로 해결할 수 있는 것일까? 하는 것입니다. 이를 위해 가장 간단한 NP형태의 문제 하나를 예로 들어 보지요.

이른바 최소 거리 문제입니다. N 개의 도시가 있고 각각의 도시간 거리가 주어졌을때 최소 거리로 N개의 도시를 이동하는 방법은 무엇인가, 하는 것이 그것입니다. 계산 과정은 실로 간단합니다. 각 경우의 수를 모두 계산해서 비교하여 최소의 경우를 찾아내면 되니까요.

경우의 수는 N*(N-1)*(N-2)...*1 = N!이 되는 문제입니다. 문제는 여기서 시작됩니다. N이 일정 수준 이하로 작을 때 이 문제는 손으로도 계산할 수 있을 만큼 쉬워집니다. 그런데, N이 조금만 커지면, 이 문제를 해결하는데 걸리는 시간은 어마어마하게 커집니다. N이 비교적 최소에 가까운 경우라고 하더라도, N!>3^N입니다. 즉, 지수 시간보다도 더 시간이 걸리는 어처구니 없는 경우가 되어 버리는 거지요. 계산은 이다지도 쉬운데 말입니다.

이러한 분류의 문제들을 이른바 NP문제, Nondeterministic Polynomial-time process라고 이름붙인 겁니다. 사실 이 NP문제는 이론상의 문제입니다. [비결정적]이라는 방식 자체가 컴퓨터에서는 쓰일 수 없기 때문이지요. 즉, NP문제에서 컴퓨터는 매번 최선의 선택을 하여 최단경로가 되는 경우를 찾아서 계산한다고 가정하는 겁니다. 이렇게 되면 NP문제는 P문제와 같은 시간에 풀리게 되는 거지요. NP 문제의 본질은, 간단한 계산이 엄청나게 많은 경우의 수를 가지고 있다는 겁니다.

이렇게 되면 NP 문제는 P와 지수 시간 사이에 위치한 문제가 됩니다. 모든 P 문제는 자동적으로 NP 문제입니다. 그러나 NP문제는? 이게 문제입니다. 모든 NP 문제가 P 문제인가, 혹은 NP문제와 P 문제는 완전히 다른 문제인가. 이것이 비교적 이해하기 쉬운 P vs NP에 관한 간단한 설명입니다.

앞서 설명한 최단 거리 문제를 경우의 수를 모두 계산하는 경우를 제하고 정확한 답을 다항 시간 이내에 구하는 방법을 찾는다면, 그 자체만으로 P=NP임을 증명하는 것이 될 수 있습니다만, 아직까지 그런 방법은 발견되지 않았지요.