저는 학교 다닐 때 자연계열이었음에도 수학을 엄청 못했습니다. 한번은 100점 만점에 25점도 받아봤고 지금도 가끔 씩 고등학교로 되돌아가서 수학시험을 보는 악몽(!)을 꾸곤 합니다. 꿈에서 보면 배경은 이곳저곳 바뀌어도 늘 시간은 고등학교 때이고 수학문제지를 받았는데 1번부터 모르는 문제가 나오고 1번을 못 풀어서 쩔쩔매다보면 어느새 감독 선생님이 시험지 걷어가겠다고 하면서 꿈이 끝나곤 합니다.

그런 제가 예전에 겁도 없이 피지알 자유게시판에 밀레니엄 수학문제 가운데 하나인 p vs. np 문제에 대한 글을 올렸다가 여러분의 날카로운 지적을 받고 개망신을 당했던 적도 있었습니다. 그냥 거기서 그만 두면 되는 데 어젯밤에 또 고등학교로 되돌아가서 수학문제를 푸는 꿈을 꾸다보니 오늘은 아침부터 갑자기 이 문제가 생각이 나서 또 인터넷을 돌아다니며 이 문제를 이해해 보려는 시도를 하게 되었습니다.

그래서 반나절을 이곳저곳 웹서핑 하면서 눈동냥을 해본 결과 제가 최대한 이 문제에 대해서 아래 정도만큼 이해를 하게 되었습니다. 과연 제가 문제의 일부분이나마 제대로 이해를 한 건지 아니면 또 이번에서 제대로 헛 다리를 짚은 건지 다시 한 번 피지알 회원님들의 준엄(!)한 심판을 받아볼까 싶어서 또 이렇게 자게에 글을 올립니다.


-----------------------------------------------------------------------------------------------------
그러니까 이 p vs. np 문제는 순수한 수학의 문제만은 아니라 컴퓨터 알고리즘과 관련이 있는 문제라는 겁니다. 저는 수알못 못지않은 컴알못이어서 이 문제도 만만치가 않은데 일단 그러니까 이 세상에는 컴퓨터로 해결하기 쉬운 문제가 있고 아무리 컴퓨터라고 하더라도 답을 내는 것이 매우 어려운 문제들이 있다는 것입니다.

예를 들어 2 + 3 의 답을 구하는 문제는 쉽게 컴퓨터 알고리즘으로 해결할 수 있다고 합니다. 더하는 숫자의 자리수가 커지더라도 컴퓨터로 쉽게 해결할 수 있는 문제라는 본질은 바뀌지 않는다고 합니다.

그리고 이런 문제는 거꾸로 답을 제시하고 이 답이 그 문제의 해답이 맞느냐고 역으로 검증하는 것 역시 쉽게 컴퓨터 알고리즘으로 해결이 가능하다고 하네요. 즉, 5는 2와 3의 합이 맞느냐?라고 하는 문제 역시 컴퓨터로 간단하게 해결이 되는 문제라는 거지요.

이렇듯 컴퓨터 알고리즘으로 주어진 문제의 답도 쉽게 구할 수 있고 역으로 어떤 주어진 답이 정말 맞는 지 검증하는 것 역시 쉬운 문제를 P문제라고 한다고 합니다.

그럼 이번에는 다른 문제를 한 번 생각해 봅시다.

예를 들어 [1.7950768632263237 x 10의 29승]은 과연 무슨 수와 무슨 수의 곱인가? 라는 문제를 컴퓨터를 사용해서 해결한다고 생각해 봅시다. 저 같은 컴알못은 이번에도 이런 문제 역시 컴퓨터 엔터키 누르기가 무섭게 답이 척 하고 나올 거라고 생각하지만 의외로 이런 문제는 컴퓨터로 해결하기가 어렵다고 합니다. 시간이 아무리 오래 결려도 해결하기가 쉽지가 않다고 하는군요.

그런데 만약 어떻게든 이 문제의 해를 우리가 알고 있고 이 해가 과연 정답인지 검증하는 문제는 의외로 간단합니다. 즉, 2569823451289563와 69852147326523의 곱이 1.7950768632263237x 10의 29승인가? 하는 문제는 간단하게 검증할 수 있다고 합니다. 제가 보기에도 그냥 두 수를 곱해서 실제로 답이 1.7950768632263237x 10의 29승인지만 확인하면 될 것 같습니다.

이렇듯 문제의 답을 구하기는 어렵지만 어떤 주어진 답이 그 문제에 맞는 답인지 검증하는 것은 쉬운 문제를 np 문제라고 한다고 합니다.

이제 사람들이 알고 싶은 것은 과연 p 문제와 np 문제의 본질이 같은 것인가 전혀 다른 것인가 하는 것이라고 하네요. 즉, 저 np 문제라고 하는 것을 우리가 컴퓨터 알고리즘으로 쉽게 해결하지 못하는 것은 단지 우리가 아직 저 문제를 쉽게 해결할 수 있는 방법을 찾지 못해서 그런 것일 뿐 그 문제를 해결할 수 있는 방법만 알게 되면 p문제처럼 쉽게 컴퓨터로 해결할 수 있을 것이다 라는 것은 p = np 의 입장이라는 겁니다.

반면에 np 문제는 본질적으로 p 문제와는 다르고 그렇기 때문에 np 문제를 컴퓨터 알고리즘으로 쉽게 해결할 수 있는 방법이라는 것 자체가 존재하지 않는다 라는 것이 p =(not) np 의 입장이 되겠습니다.

즉, p vs. np 문제는 “p = np” 냐 아니면 “p는 np가 아니냐” 라는 것을 수학적으로 증명하라는 문제가 되겠습니다. 만약 p = np 라는 게 사실이라면 이 세상은 어제와는 전혀 다른 신세경이 펼쳐질 거라고 합니다...
------------------------------------------------------------------------------------------------------


여기까지가 제가 이해한 p vs. np 문제의 전부입니다. 만약 p vs. np 문제가 이런 게 아니라면 저는 이제까지 늘 그랬듯이 앞으로 계속 수포자로 살면서 수학문제 못 푸는 악몽이나 계속 꾸겠습니다...어차피 수알못으로 산 인생이 어언 40년이 넘었는데 여기서 뭐가 더 두렵겠습니까?...--;;;