| [ QuizWit ] in KIDS 글 쓴 이(By): darkman (아랑타불) 날 짜 (Date): 2003년 12월 29일 월요일 오후 09시 15분 33초 제 목(Title): CMI문제 P vs NP 아노니서 논란이 되고 있는 CMI문제들에 대해 정리해보겠습니다. 홈페지 자료와 Keith Devlin이 쓴 The Millennium problems 를 참고해서. 전 물리쟁인데 이론물리를 하다보니까 7문제 대부분이 그동안 연구해온 분야와묘한 연관이 있군요. 여기 선택된 문제들은 대부분 타분야의 응용가능성을 염두에 둔게 아닌가 싶습니다. 우선 문제의 P vs NP문제에 대해 논해봅시다. 이보드 위에 잘 정이돼 있지만 P=Polynomial란 입력의 크기 N에 대해 푸는 시간이 N의 다항식 오더로 걸리는 문제라고 할 수 있죠. 한마디로 컴퓨터로 쉽게 풀수 있는 문제들이고 NP는 non polynomial이 아니고! Nondeterministic polynomial로 일반 컴퓨터와 달리 확률적으로 정답을 잘 찍는 즉 어떤 힌트가 주어지는 가상의 컴퓨터가 있어서 그것이 폴리노미말 시간안에 풀수 있는 종류의 문제들을 말합니다. NP는 다른 관점에서 답이 주어질 때 그 답이 맞는지 틀린지를 보통 컴퓨터로 폴리노미알 시간안에 확인할 수 있는 문제들로 봅니다. 예를 들어 영화 큐브에서 자폐증 청년이 문에 쓰인 수를 소인수 분해 (아니면 소수인지 확인?)하는데 어떤 로직이 아니라 그냥 머리에서 턱 떠오르는 직감으로 풀죠? 그의 뇌가 Nondeterministic컴이라 생각해볼 수 있겠습니다. 그럼 딴 범재들도 그 소인수분해가 맞는지는 쉽게 곱셈으로 확인해볼수 있죠. 고로 소인수분해는 NP입니다. (여기까지 오류가 있으면 지적해주십쇼) 수를 소수곱으로로 분해하는건 RSA암호키등 많은 수학쟁이들의 밥줄이니 아주 중요하죠. 그런데 P는 NP에 속합니다. 왜냐 답을 직접풀어버리면 답을 확인하는것과 마찬가지니까. 그럼역으로 남은 문제는 NP는 P에 속하느냐 그러니까 두개합치면 NP=P냐는 질문이 나오게되죠. 그러니까 "우리가 답이 맞는지 쉽게 검산할 수 있는 문제가 항상 쉬운 해법이 있느냐(알려져있던 아니던)"는 겁니다. 앞으 예로 어떤 수C를 A*B로 분해하는 문제에서 A,B를 천재적인 머리나 영감이나 찍어서 알아낼수 있을때 답이 맞는지는 쉽게 알수 있는데(NP) 그렇다면 소인수분해를 쉽게 할수 있는 알고리즘이 존재하지 않는가 하는 의문입니다. 물론 많은 학자들은 NP!=P라고 생각하는거 같습니다. RSA암호체계등이 소수분해가 자리수가 커짐에따라 기하급수적으로 시간이 걸린다른걸 이용하는거니까 P인 알고리즘이 존재한다면 당장 난리가 납니다. 사실 양자컴퓨터가 인기를 끈 이유는 SHor가 양자컴이 있다면 확률적으로 다항식시간안에 소수분해를 할수있다는걸 보였기 때문이죠. 고로 백만불을 버는 한가지 방법은 NP에 속하지만 P에는 안 속하는 "단한가지 예"라도 있음을 보이면 됩니다. 자기만의 문제를 만들어도 됩니다. 소수분해의 예에도 P시간으로 풀수 있는 알고리즘이 없다고 아무도 증명못했습니다. (지금 모 한국수학자가 증명했다는게 이런 예를 하나 찾았다는거죠) 또다른 증명방법은 NP complete를 이용하는겁니다,. NPcomplete란 traveling sales person 문제처럼 NP문제중 어려운 분류로 이문제와 다른 NP문제들간의 변환이 P시간안에 이뤄지므로 만약 NP complete중 "하나라도" P시간안에 풀수 있다면 모든 NP들이 P에 속한다는걸 증명하게 되는거죠. 이런 NP complete들이 많은데도 하나도 P시간에 풀수 있는 알고리즘이 발견되지 않는 점이 NP!=P라고 믿는 이유중하나일거고,. 고로 쉬운 NP complete문제를 하나 만들어서 그게 P임을 보이는 방법도 있다는겁니다. 제 개인적 의견으론 이문제는 한가지 반례만 찾아도 되고 어택할수 있는 전문가들이 수학자 전산한자 물리학자등 많으므로 젤먼저 해결되지 않을까 합니다. (아노니 보니 누가 포앙카레 콘젝쳐에 대해 유력한 증명을 했다고 하는군요) |