100만달러(12억원) 현상금이 걸린 20세기의 수학 난제가 풀릴 전망이다.

전북대 김양곤(55·수학 통계정보과학부) 교수팀은 24일 “미국 클래이 수학재단(CMI)이 지난 2000년 상금 700만달러를 걸고 발표했던 이학계의 세계 7가지 난제 중 1번 문제를 풀었다.”고 밝혔다.김 교수는 미국 위스콘신 대학 남기봉 교수와 함께 1번 문제인 ‘P 대(對) NP’를 공동으로 해결,2004년 3월에 발표되는 인도의 SCIE급 논문집 ‘Journal of applied algebra and discrete structure(JAADS)’에 게재할 예정이다.

김 교수의 논문은 게재후 2년간 수학계의 반응을 본 뒤 CMI의 심사를 거쳐 100만달러 수상 여부를 결정하게 된다.수학의 발전·보급을 목표로 활동하고 있는 CMI는 2000년 ‘P 대 NP’,‘리만 가설’,‘내비어-스토크 존재와 매끈함’,‘양-밀즈 존재와 매스 갭’등 일반인들은 들어보지도 못한 수학계의 7개 난제에 대해 개당 100만 달러의 현상금을 내걸었다.

이 문제들은 내로라 하는 수학자들도 이미 두손을 든 것들로 정답이 나올 때까지는 수년 혹은 수십년이 걸릴 것으로 추정됐지만 김 교수팀은 3년 만에 문제를 풀어 7개 문제 가운데 처음으로 논문 게재를 승인받았다.

당시 CMI의 아서 제퍼(하버드대 수학교수) 이사장은 “시한은 없다.”면서 “빠르면 4년 이내에 정답이 하나 정도 나올 수 있을 것으로 기대한다.”고 말했다.

김 교수가 푼 ‘P 대 NP’는 컴퓨터 알고리즘과 관련된 분야로 수학의 귀납법 풀이는 가능하나 연역적 풀이도 가능한가 하는 문제이며,이 가운데 NP 복잡도는 지난 98년 IBM과 MIT의 양자 물리학자들이 정수의 소인수 분해를 다항식으로 만드는 알고리즘을 개발해 앞으로 10∼20년 뒤에 해답이 나올 것으로 예측했다.

김 교수는 전북대를 졸업한 뒤 캐나다 토론토대학에서 박사학위를 받았으며,현재 전북대 순수 및 응용 수학연구소장직을 맡고 있다.

그는 “인류 태동 이후 마음속으로만 생각했던 기이한 문제들에 대한 해법을 수학적 이론으로 정리한 것이 성과”라면서 “이론적 증명이 가능해졌기 때문에 이제 과학기술만 병행 발전된다면 상당수의 수수께끼와 의문들이풀릴 수 있을 것”이라고 말했다.

전주 임송학기자 shlim@

■‘P對 NP'는 어떤 문제

전북대 김양곤 교수가 ‘이학계의 세계 7가지 새 천년 문제’ 중 1번 문제를 해결한 것은 미지의 에베레스트산 봉우리 가운데 하나를 최초로 정복한 것과 같다는 평가를 받고 있다.

김 교수는 그동안 혼신의 힘을 다해 풀이를 이끌어낸 이 문제의 해답을 인정받기 위해 미국 학계에 2차례나 신청했지만 받아들여지지 않았다.

그러나 수학계에서 세계적으로 인정받는 인도에서 김 교수의 논문을 인정해주어 빛을 보게 됐다.

김 교수는 “이 문제의 해답은 수학계 최고 석학들이 알아볼 수 있도록 작성할 경우 A4용지로 24쪽에 이르고 박사급이 이해하려면 240쪽,대학원생이나 학부생이 이해하려면 2400쪽으로 풀어써야 할 만큼 복잡하다.”고 말했다.

그는 “이번 문제가 해결됨으로써 그동안 미지의 문제에 대한 분류작업이 가능해져 각종 이론 발전에 촉매 역할을 하게 될 것”이라고 말했다.

문제 원문은 다음과 같다.

A problem is P if it can be solved by an algorithmthat runs in polynomial time(that is,the running time is at most a polynomial function of the input). A problem is in NP if a proposed solution can be checked in polynomial time. Does P=NP? 어떤 문제가 다항 시간내에 동작하는 알고리즘(최대 해결 시간이 입력의 다항 함수로 표현되는 알고리즘)으로 풀이될 수 있으면 P에 속한다.어떤 문제의 제시된 해답이 다항 시간내에 검토될 수 있으면 그 문제는 NP에 속한다.P=NP인가?

전주 임송학기자