NP문제에 대한 간략한 소개가 있으면 좋겠습니다. 페이지 이름도 약간 적절하지 못한 듯 합니다.
NP problem을 어떻게 해결할 것인가는 금세기 전산학에서 가장 중요한 문제 중의 하나일 것이다.
그 해결책의 한 방법으로 DNA의 상보적인 결합 반응을 이용해서 문제의 해결책을 찾아내는 DNA computer라는 것이 존재하는데, 이것은 time complexity를 space complexity로 대치하는 효과를 가지고 있다. 따라서 space만 충분하다면 NP problem들도 이론적으로는 해결할 수 있다. 하지만 문제는 space가 증가할 때 DNA들의 균질한 반응을 만들어 낼 수 없다는 것이다. 1.5ml 의 Ependorf tube에서는 균질한 반응이 일어날 수 있겠지만, 사람 크기만한 tube에서는 그렇지 못할 것이기 때문이다.
상황을 바꾸어서 이러한 경우를 생각해 볼 수 있다. 이 사회 또는 인류, 나아가 지구 전체를 하나의 문제 해결을 위한 도구라고 본다면?
전체적인 문제 상황이 주어질 때, (혹은 진화의 압력이라 해도 무관할 것이다.) 각 개체별로 어떤 해결책을 TestFirstProgramming 방식으로 추구하게 될 것이다. 이것이 압력이 주어진 이후에 만들어진다기 보다는, 이미 내부적으로 수많은 안들을 가지고 있는 것 중에서 하나가 선택되어지는 경우가 더 많을 것이다. 따라서 해결 방법 모색의 복잡성도 O(n)이 아니라 O(nm)일 것이다. (n=전체개체수, m=개체내에서 모색되는 대안들). 시간이 지날수록 가능성은 O((nm)^t)로 기하급수적으로 증가한다. (t=경과된 시간)
그리고 이러한 하나 하나의 해결책들이 서로 만나면서 마치 DNA가 상보적으로 결합하는 것처럼 성장하게 된다. 물론 여기서도 생명체나 존재 전체가 동일하게 공유하는 어떤 정보의 network가 이루어져 있다고 가정하지 않는다면, 균질한 반응은 기대하기 힘들 것이다. 하지만 최소한 인간은 인터넷 덕분에 훨씬 균질한 반응을 이끌어 낼 수 있게 되었다. 그리고 어쩌면 균질하지 않은 반응이 오히려 열쇠일지도 모른다. 예를 들어, 결혼을 정말 random하게 아무하고나 하는 사람은 없다. Random하지 않은 것이 MonteCarloMethod와의 차이가 될 수도 있을 것이다.
물론 이것이 NP problem을 근본적으로 해결할 수 있다는 것은 아니지만, 어쨌든, 복잡한 문제의 근사해를 찾을 수 있는 하나의 방안이 아닐까? --지상은
실제로 생물이 찾아낸 해법은 최적해가 아닌 근사해인 경우가 많다. 생명체가 사용하는 방법이 근사해라는 건 어찌보면 진화를 입증하는 가장 훌륭한 증거가 아닐까?
NP problem 중에는 실제로 자연상에서는 쉽게 일어나는 일들도 있다. 이는 우리가 너무 과거의 수학적 접근으로만 문제를 해결하려는 데에도 문제가 있다고 본다. 간혹 생각을 해본다. 우리가 지금까지 알고 있던 수학의 범위가 (만약 있다면) 실제로 존재하는 수학의 얼마를 차지하는지.. --picxenk 장난으로 생각해본 이상한나라의수학단백질의 3차 구조가 근사해일까요??
자연은 TuringMachine의 한계에 구속받지 않는 거대한 QubitDotOrg입니다
양자컴퓨터란 그저 물리학의 한 모델인 양자역학에서의 해공간, 즉 Hilbert space에서 computation을 함으로써 이진수기반의 노이만형컴퓨터에서 벗어나겠다는 것인데, 양자컴퓨터를 자연이라고 말하는 건 비약이라고 생각합니다.
SeeAlso PNPProblem양자컴퓨터란 그저 물리학의 한 모델인 양자역학에서의 해공간, 즉 Hilbert space에서 computation을 함으로써 이진수기반의 노이만형컴퓨터에서 벗어나겠다는 것인데, 양자컴퓨터를 자연이라고 말하는 건 비약이라고 생각합니다.