출처 : http://www.semtl.co.kr/cgi-bin/science_cont_view.cgi?dir=&id=pds/math
&page=3&action=view&number=10
싸고 좋은 물건을 사기 위해 이 가게, 저 가게 들러서 가격별로, 기능별로 목록을 작성하는 경우가 있다. 알뜰 구매를 하기 위해 조건에 맞춰 최선의 선택을 위한 정보를 수집해서 분석해 보는 것이다. 당연히 많은 가게를 알아보면 정리하는 시간이 많이 걸린다.
이렇게 일상 생활에서 문제가 주어지고 그것을 해결하기 위한 조건을 정하고 정답을 찾는 행위는 의식적인든 무의식적이든 항상 하고 있다.
그 런데 알뜰 구매같은 문제보다 훨씬 복잡한 문제에 부딪힐 때도 많다. 예를 들면 서가에 여러가지 종류의 책을 정리하는 경우다. 120권의 책을 3단 책꽂이에 정리한다고 치자. 크기, 모양, 장르, 꺼내는 빈도등 각종 기준이 많을 수록 최적화된 정리 순서를 결정한다는 것은 쉽지 않다. 이론적으로는 120!의 가짓수 중에 선택해야 하는 것이고 이것을 컴퓨터로 뽑아내는 것도, 그 중에서 골라 내는 것도 그리 쉬운 일이 아니다. 그러나 누군가 정리한 상태를 보고 관찰자가 자기 기준에 맞는 지를 검증하는 것은 어렵지 않다. 검증은 쉽지만 정답은 찾기 힘든 이런 문제를 수학에서는 비결정적 시간 다차항식 문제(NP, Nondeterministic-Time polynomial Problem)라고 한다,
알뜰 구매를 위해 알아본 목록을 가격별로 정리해내는 것은 일종의 수열 정리( Sorting )이다. 알고리즘으로 이진 트리를 쓰던 버블 소팅을 하던 푸는 시간은 항목의 갯수에 따르는 다항식으로 표현할 수 있다. 문제 해결 시간이 문제에 포함된 인수의 다항식으로 표현될 수 있는 문제를 다차항식 시간 결정 문제( P, Deterministic-Time Polynomial Problem)이라고 한다.
|
그렇다면 즉 P ⊆ NP 라는 포함관계를 인정할 때 P 가 NP와 같은지 아니면 P 문제가 아닌 순수한 NP문제가 있느냐? 는 질문을 할 수 있다. 이 두 집합이 동치라면 지수 함수적인 해결 시간이 걸리는 NP문제로 P에 준한 현실적인 알고리즘을 적용할 수 있게되는 것이 자명하다.
일상에서 부딪히는 어떤 문제를 쉽게 풀 수 있는 '꽁수'는 언제나 있을까?
만 약에 '꽁수'가 없는 문제라고 '생각'해 버리면 문제를 컴퓨터 따위로 해결해보려는 생각따위는 시간 낭비에 지나지 않는다. 그러나 '꽁수'가 항상 있다고 '생각'한다면 구식 컴퓨터라도 '천재적인 알고리즘'을 짜 넣기만 하면 세상에 풀리지 않을 문제는 없다. 아무리 어려운 암호라도 결국은 풀 수도 있다. 암호라는 것이 이론적으로 존재할 수 없다고까지 할 수 있다.
어려운 문제도 쉽게 풀 길이 있을까? 이런 의문에 대해 계속 연구가 이어지고 있다.
http://www.cs.bu.edu/fac/lnd/toc/
http://www.cs.toronto.edu/~sacook/
http://ural.wustl.edu/~slstrick/compgen_pres/sld001.htm
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
http://www.dm.ufscar.br/hp/hp501/hp501001/hp501001.html
http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf
http://www.win.tue.nl/~gwoegi/sipser.pdf
100만 달러 달린 수학문제 국내 교수들이 풀 듯…심사 최종단계
| 1971년 네오니드(Leonid Levin), 스테판(Stephen Cook)이 문제를 제기했다. 계산하기 어려운 문제도 결국은 쉬운 해법으로 계산하여 풀 수 있는가이다. P Problem(Polynomial Time Problem) : 문제에서 주어진 인수로 구성된 다차항 함수의 시간을 소요하는 계산으로 '쉽게' 풀 수 있는 문제. 답을 찾기 쉽다. |
 ▲ Leonid Levin |
 ▲ Stephen A. Cook |
○…100만달러(약 12억원)의 현상금이 걸린 20세기 수학 문제가 국내 연구팀에 의해 풀릴 전망이다.
전 북대 김양곤(56·수학 통계정보과학부)교수팀은 “미국 클래이 수학재단(CMI)이 지난 2000년 상금 700만 달러를 걸고 발표했던 세계 7가지 난제 가운데 1번 문제를 푸는데 적용했던 ‘S-이론’이 CMI가 공인한 논문 평가 저널인 매스사이넷(MathSciNet)에 게재됐다”고 14일 밝혔다.
김 교수는 2003년 미국 위스콘신 대학 남기봉교수와 함께 1번 문제인 ‘P 대(對)NP’를 공동으로 해결,이듬 해 3월 인도의 SCI급 저널인 ‘JAADS’에 게재한 바 있다.
‘S -이론’은 김 교수팀이 P 대 NP 문제를 풀기 위해 개발,적용한 수학 원리로 이번에 매스사이넷에 초록이 게재되면서 CMI의 자체 심사를 거쳐 문제를 푼 것으로 인정받는 최종 단계에 한발짝 다가서게 됐다. 김 교수는 “매스사이넷에 ‘P 대 NP’ 해법과 관련한 논문이 실린 것은 이번이 처음”이라며 “최종 승인을 받는 절차에 본격 돌입할 수 있게 됐다”고 주장했다.
그러나 이러한 김 교수팀의 해법은 이 문제를 심사하게 될 심사위원들조차 모를 가능성이 커 2년여에 걸친 심사기간 수학계의 반응이 큰 영향을 미칠 것으로 알려져 왔다.
‘P 대 NP’는 컴퓨터 알고리즘과 관련된 분야로 예를 들어 외계에 생물체가 있는가 혹은 귀신은 존재하는가 등의 질문에 대해 ‘그렇다’는 가설을 세운 뒤 컴퓨터를 활용,이론적으로 완벽한 증명을 해내는 것을 뜻한다.
전주=김용권 기자 
ygkim@kmib.co.kr 국민일보, 쿠키뉴스 2005-12-14
