컴퓨터를 이용한 수학문제 증명

때로는 아주 간단해 보이는 문제가 해결에 오랜 시간이 걸리는 경우도 있다. 케플러(1571-1630) 의 추측이 그러한 문제이다. 페르마의 정리는 x^n+y^n=z^n의 자연수는 n>=3인 경우에는 없다, 4색 문제는 “지도의 인접한 국가들을 겹치지 않고 표시하는데 4색이면 된다” 처럼 간단하다. 케플러 추측도 단위 부피에 둥근 공을 가장 효율적으로 배치하는 방법이 무엇인가이다. 이미, 과일장수들도 알고 있던, 먼저 1층의 원을 쌓고, 빈 틈에 2층을 올리고, 그 위의 빈틈에 다시 과일을 쌓는 방업이다. 케플러가 16세기에 그 방법이 최선일 거라고 당연한 추측을 했지만 400년이 지나 20세기에 와서야 컴퓨터의 도움을 받아서 증명한다. 

 

아래 왼쪽 그림과 같이 아래위로 공을 쌓으면 이것을 단순 입방 구조 (simple cubic, sc)이라고 부른다. 이렇게 쌓으면 전체 공간 중, 빈 공간의 비율이 48%이다. 두번째 방법은 두 원 사이를 조금 떨어뜨리고, 그 위에 새로운 공을 쌓고 이를 반복하는 구조이다. 이것을 체심 입방 구조 (body centered cubic, bcc)라고 부르며 이 경우 충전율은 68%로 증가한다.

 

최적의 구조는 누구나 알고 있듯이, 아래층에 빽빽하게 원을 채우고, 빈 공간에 다시 원을 채우고 그것을 반복하는 아래와 같은 면심 입방 구조이다 (face centered cubic, FCC). 이 경우 최대 74%의 공간을 활용할 수 있다. 만약, 규칙적인 격자 구조를 가정하는 경우는 가우스가 최적이라는 것을 증명하였다. 그러나, 만약 규칙적이지 않다면? 거의 무한한 조합이 가능하기에 증명이 쉽지 않다.

 

이 문제는 제안된지 387년이 지난 1998년에 미국 수학자 헤일스(Thomas Callister Hales)가 컴퓨터를 이용하여 증명한다. 3G 바이트의 방대한 데이터와 250쪽의 논문을 검증할 수학자는 세상에 없다. 따라서, 다들 “걍 맞겠지.. 재네들 불쌍하잖아.. 개고생했는데..”라고 넘어간다. 그 후 2017년에 헤일스팀이 다시 논문을 잘 작성하여 논문 review를 통과한 후 2017년에 논문이 출판된다. 컴퓨터를 이용한 증명을 증명이라고 불러야 하나? 오늘날 수학자들의 고민거리이다.

 

비슷한 문제로 4색 정리가 있다. 4색문제는  1852년 식물학자 프란시스 구스리가 영국지도를 칠하다가 4색만으로 겹치지 않게 칠할 수 있다는 사실을 발견하고 이것이 일반적인 것인지를 영국의 수학자 드 모르간(August de Morgan, 1806-1871, Boolean logic 혹은 set theory의 DeMorgan’s law로 유명)에게 질문하면서 시작된다. 얼핏 쉬워 보이는 이 문제는 가능한 경우가 거의 무한대처럼 많기에 쉽지 않았다.

 

결국 100여년이 지나서 1960년 독일의 헤쉬가 그래프 이론을 적용하여 가능한 모든 지도를 9000개 정도의 패턴으로 분리하고 이것을 컴퓨터로 증명할 것을 제안하지만 계산에만 10년이 걸리는 일에 돈을 댈 사람이 없어서 포기한다. 그 이후 1976년 미국의 하켄과 아펠이라는 두 수학자가 가능한 패턴을 1936개로 줄인 후, 컴퓨터 2대를 50일 동안 돌려서 증명에 성공한다. 케플러 추측과 마찬가지로 엄청난 양의 데이터와 몇 박스의 자료를 검증할 사람은 없다. 여러 컴퓨터로 계산 과정의 오류가 없는지 체크하는 아름답지 못한 방법으로 오류를 검증한다.

 

22년전, 그 당시만 하더라도 생소한 인공지능을 박사학위 주제로 공부하던 후배가, 자신은 자신의 논문을 쓸 인공지능을 개발해서 졸업하겠다고 얘기했다. 속으로 “개 또라이 아냐?”라고 생각했지만, “멋지다. 꼭 졸업해라”고 격려했다. 아마 제대로 졸업하지는 못했을 것이다. 

 

어쨌던, 오늘날 여러 수학 문제들을 컴퓨터가 증명하고 있다. 아직은 알고리듬 레벨의 논리전개는 아니지만, 어떤 정해진 범위 내의 가능한 모든 방법들은 컴퓨터가 훨씬 효율적으로 찾아내는 것이다. “이러다 모든 어려운 일들은 인공지능이 하고, 인간들은 인공지능이 안하는 허드렛 일들만 하는 것 아냐?” 누가 농담삼아 얘기하지만, 그 날이 그리 멀지 않을 것임을 느낀다. 며칠전 기사에 인공지능 개발을 위해서 training data를 구분하고 label을 붙이는 단순한 알바가 인기라고 한다. 문제는 인공지능이 풀고, 그들을 위한 데이터를 제공하는 단순한 잡일(속칭 노가다)를 인간들이 하는 것이다. 

 

 

4색문제를 해결한 두 수학자의 말을 나무위키에서 인용해 보자. 

 

“어느 순간 부터인가, 컴퓨터가 우리를 놀라게 하기 시작했습니다. 처음에 우리는 계산에 필요한 변수들을 일일이 손으로 입력하면서 작업을 했기 때문에 어떤 상황에서든 컴퓨터의 모든 동작을 미리 예견할 수 있었습니다. 그런데 갑자기 컴퓨터가 체스를 두는 로봇처럼 혼자서 돌아가기 시작했습니다. 컴퓨터는 자신이 '학습했던' 모든 방법들을 하나씩 적용해 나가면서 계산을 했고, 어떤 때는 사람보다도 현명한 판단을 내리곤 했습니다. 그 이후로 우리는 계산을 어떻게 진행해야 할지 컴퓨터에게 배우는 신세가 되었습니다. 어떤 면에서 볼 때 컴퓨터는 계산 능력뿐만 아니라 지적인 능력까지도 자신의 창조주인 인간을 능가하고 있었습니다.”