미국의 클레이 수학 연구소에서는 2000년을 맞이하야 7가지 난제를 내놓고 각 문제당 상금 100만불을 걸었습니다. 다음과 같은 문제들인데요 Birch and Swinnerton-Dyer Conjecture Hodge Conjecture Navier-Stokes Equations P vs NP Poincaré Conjecture Riemann Hypothesis Yang-Mills Theory 이 중에서 가장 만만해 보이는(?) 문제가 P vs NP 문제입니다. 양-밀즈에 관해서 ExtraD님이 써주시기를 바라면서 P vs NP 와 계산이론에 대해 간략히 설명해볼게요... (gigantul님은 리만가설이나 포엥카레 컨젝쳐 하나 맡아주시고 유체하시는 분 아무나 나비어-스톡스 맡아주시면 감사..) 현대수학에서 괴델의 불완전성 정리로 인해 계산가능성의 문제가 수학에 제기되자, 여러 학자들은 계산 가능한 문제의 집합을 정의하려는 여러 노력을 시도했고, 그 결과 Church의 lambda calculus, post의 post system, markov의 markov algorithm, recursive function theory같은 여러 이론들이 난립(?)을 하게 되는데, 이렇게 서로 다른 정의와 가정에서 출발해서 도출한 자동화 문제풀이 도구들의 문제풀이능력이 서로 다 같고, 그리고 이 모델들이 풀 수 있는 문제집합이 알고리즘을 이용해서 풀 수 있는 모든 문제와 일치할 거다..라는 church-turing thesis (처치-튜링 논제.. 아직 증명이 안되어서 정리라고 부르지는 못합니다만 대부분 그냥 옳겠거니 하고 쓰고 있습니다.)를 주장하게 됩니다. 이 정의에 따라, 아마 전산 전공자들은 알고계실 Finite Automata같이, 자동화된 문제 해결기계를 만들어서 가장 강력한 FA를 가정하게 되면 이게 바로 튜링 머신입니다. 그러면 이제 이 머신을 이용해서 풀 수 있는 문제들을 다시 분류를 지어볼 수 있습니다. (물론 괴델의 정리에 따라 당연히 못푸는 문제들이 존재하고, 이 문제들은 FA로 풀 수 없습니다. 가장 대표적인 것이 halting problem으로, 옳은지 그른지를 결정하는것 자체가 불가능합니다.) 우선 P라는 문제들의 집합을 정의합니다. 이 문제는 polynomial의 앞자를 딴것입니다. 간단히 얘기하자면 정해진 시간 내에 풀 수 있는 문제가 됩니다. (사실 훨씬 복잡합니다만...=_= 더 얘기하다간 손님 다 떨어질 것 같아서...) 그리고 NP라는 문제집합이 있는데, 이 문제는 정해진 시간 내에 풀 수 있는지 모르겠지만, 답이 주어지면 이 답의 옳고 그름을 정해진 시간 내에 검사할 수 있는 문제집합입니다. 당연히 P는 NP의 부분집합이 됩니다. (걍 풀어서 검산하면 되니까..) 근데 NP=P일까? 라는게 현대 계산이론의 가장 큰 난제로 떠오르게 됩니다. 왜냐하면, NP라고 알려진 많은 문제들이 우리가 풀고 싶었지만 정해진 알고리즘 이 없어서 손을 놔버린게 많은데, NP=P라면 정해진 시간 내에 문제를 풀 수 있다는 보장이 생기게 되기 때문입니다. 그러면 어떻게 NP가 P와 같거나 아님 다르거나를 증명할 수 있을까요.. NP나 P나 문제들의 집합이기 때문에, 이 둘을 비교하려면 모든 원소를 비교해야 할것처럼 생각되어서 해결의 실마리가 전혀 없었습니다. 그런데 Cook이란 사람이 어떤 문제가 NP-complete라는 걸 발견했습니다. NP-complete란, 다른 모든 NP가 이 문제로 정해진 시간내에 변환되는 문제입니다. 즉, Cook이 CNF-satisfiability란 문제를 (몰라도 됩니다. -_-;) 정해진 시간 내에 풀면 다른 모든 NP도 정해진 시간 내에 풀 수 있다는 사실을 발견하자, 결국 NP=P인지의 여부는 수많은 NP-complete 문제들 중의 단 한문제만 풀어도 해결이 되게 되었습니다. 그 중에 TSP라는 유명한 문제가 있습니다. 즉 여러 도시를 여행하는 세일즈맨이 있는데 이 도시를 모두 통과하는 최단 거리를 찾는 문제입니다. 이렇게 현실적인 (?) 문제 하나가 정해진 시간 내에 풀린다는걸 증명 또는 반증하기만 하면 100만불을 받을 수 있습니다. 재야수학자들의 (각의 3등분론자, 페르마의 정리 증명자 같은..) 많은 참가를 바랍니다... -_-;; p.s. 사실 NP-hard, PSPACE, EXPTIME 등의 다른 레벨의 시간이나 자원이 소요되는 문제들의 집합 도 있습니다. (대표적인게 바둑.. PSPACE problem이죠..) 하지만 이것까지 설명하려다간 날샐거 같아서.. p.s.2. 소수판정은 P에 속한다는 증명이 나왔습니다. 많은 사람들이 NP가 아닐까 해서 열심히 풀어보려 던 문제중에 하나였는데.. -_-; p.s.3. 가끔 신문기사중에 P=NP이면 현재 쓰는 암호체계가 다 깨지는 것처럼 표현을 하는 기사가 있던데 이건 아닙니다. 우리가 쓰는 암호체계 (RSA를 비롯해서..)의 대부분은 NP에 속하지 않는 문제에 기반을 두고 설계되어 있기 때문에, P=NP더라도 암호와는 직접 연관되지 않을 수 있습니다. (물론 연관될 수도 있고요...)