P=NP 풀어!

Tags:

<100만달러짜리 수학 난제 풀어>

(전주=연합뉴스) 홍인철 기자
100만달러(약 12억원)의 현상금이 걸린 20세기 수학 난제가 풀렸다.

전북대 김양곤 교수(55.수학 통계정보과학부)팀은 24일 “미국 클래이 수학재단( CMI)이 지난 2000년 상금 700만달러를 걸고 발표했던 이학계의 세계 7가지 난제 중 1번 문제를 풀었다”고 밝혔다.

김 교수는 미국 위스콘신 대학 남기봉 교수와 함께 1번 문제인 `P 對 NP’를 공 동으로 해결, 2004년 3월에 발표되는 인도의 SCIE급 논문집 `Journal of applied al gebra 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년 해답이 나올 것으로 예측했다.

예를 들면, 외계에 생물체가 있는가 혹은 UFO, 귀신은 존재하는가 등의 질문에 대해 ‘그렇다’는 가설을 세운 뒤 컴퓨터를 활용, 이론적으로 완벽한 증명을 해낸 것 이다.

그러나 이러한 김 교수의 해법은 이 문제를 심사하게 될 심사위원들조차 모를 가능성이 커 수학계의 반응이 매우 중요하다고 그는 설명했다.

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

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

———————

아 이제 무한한 가능성의 시대가 열리는군요.. ^^;;;

두 교수님이 해놓으신 풀이가 맞다면, computer science에 새 시대가 열린 셈인데… 이제 막 생겨난 광활한 분야에서 제가 해볼 수 있는 일들이 좀 있을런지… 아 오늘 무지무지 기쁩니다… 저 논문도 꼭 좀 보고싶은데…

두 분이 푸신 P=NP 문제는 우리가 알고 있는 그 P=NP문제 바록 그것입니다. CMI의 official problem description 은 P vs NP 문제를 ‘The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time.’ 이라고 말하고 있습니다. (http://www.claymath.org/Millennium_Prize_Problems/P_vs_NP/_objects/Official_Problem_Description.pdf)

그러니까 변형문제나 단순화된 문제도 아니고 바로 그 P=NP를 풀었단 이야기이죠..

자 이문제를 잘 모르신다면, 다음과 같은 예가 CMI에서 제공되고 있습니다.

[quote]
Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair from taken from your coworker’s list also appears on the list from the Dean’s office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.
[/quote]

(http://www.claymath.org/Millennium_Prize_Problems/P_vs_NP/)

수년내에 세상의 모든 이공계학문에 충격적인 파급효과가 발생할 것 같네요.. 특히 컴퓨터가 적용되는 분야라면 지금껏 할 수 없다고 보여져왔던 모든일들에 대한 가능성이 보장되버린 것입니다….

이건 괴델이 세상의 모든 문제를 consistent 한 시스템으로는 풀 수 없다고 증명한이후로 인류의 역사를 크게 바꿔버릴 대사건이네요… 이제 두 교수님의 위인전도 나오고 타임지에도 실리고 두 교수님은 좋으시겠어요..

Comments

5 responses to “P=NP 풀어!”

  1. 철은 Avatar
    철은

    P=NP란 말인가요..
    허.. 이것 참.. 몇년 후면 알고리즘 시간에 그 증명갖고 낄낄대겠군요.. -_-

  2. 쭌 Avatar

    이거 공대생들이 또 고생하게 생겼군.. 이젠 외우는건 그만 좀 나오면 안돼나? ㅡ,ㅡ

  3. 복연 Avatar
    복연

    잘못하면 세상이 발칵 뒤집히겠구만..
    이 문제에 기반하는 암호화 기법들이 산적한데..
    잘못하면 금융 시스템 (전자 상거래 포함) 완전 마비될 수도..
    기뻐할 일만은 아닌듯…

  4. 민구 Avatar
    민구

    쿡-레빈 theorem에서 CIRCUIT-SAT 가 NP-COMPLETE임을 보이면서 매우 일반적인 임의의 NP문제가 NP-COMPLETE 로 갈 수 있음을 보였었지.

    괴델도 마찬가지로 임의의 명제가 증명가능한가의 여부를 보이기위해 괴델 넘버링을 사용해서 모든 명제를 표현하는 일반적인 방식을 설명했고..

    아마도 (어떤 증명인지는 난 봐도 모를것 같지만) 저 교수님역시 일반적인 NP(아니면 NP-COMPLETE)을 P로 polynomial time에 reduce했을거야.. 그렇다면, 임의의 NP문제가 P에 풀릴 수가 있음을 보이기만 했을 것이고, 결과적으로 ‘어떻게 임의의 문제를 P로 풀어내는가’에 대한 모든 알고리즘이 나오지는 않은 것으로 추측한다. 아마도 이번에 나온 증명은 NP가 P이다 라는 것만 보였을 것이고, 그래서 컴퓨터가 할 수 있는 일의 경계선을 확실히 그어준 정도가 아닐까생각해.

  5. 민구 Avatar
    민구

    그리고 암호알고리즘을 뚫기가 어려운 본질은 매우 큰 integer를 factoring하는게 어렵기 때문(이라고 알고리즘 책에서 그러더라)이지…

    factoring 문제가 NP인것은 쉽게 알 수 있지만, 설사 P라고 할지라도 알고리즘을 고안해내는게 쉽지는 않을 것이야.. 특히나 수백년동안 계속해서 불가능했다는 점을 생각한다면.

Leave a Reply

Your email address will not be published. Required fields are marked *