| [ PhilosophyThought ] in KIDS 글 쓴 이(By): chopin (**쇼팽**) 날 짜 (Date): 1999년 3월 15일 월요일 오전 01시 21분 36초 제 목(Title): [계층구조론] 계산불능에 대해서 계산불능에 대해. 여기서 자꾸 발생하는 오해를 막기 위해 한가지 설명을 해야겠습니다. 공학적인 문제해결을 위해서는 허용가능한 오차내에서 문제를 푸는 방식이 사용됩니다. 이 방식이 가능하려면 오차를 줄이는 정도만큼 필요한 관찰데이타가 "log적으로"비례하여 증가해야 한다는 사실입니다. 즉, 오차를 반(1/2)으로 줄이기 위해서 관찰데이타가 한개(혹은 정수개 )가 더 필요하면 이문제는 공학적으로 해결가능하다고 말합니다. 수치해석에서 근을 구하는 문제의 경우 관측을 한번 더 하면 오차는 그의 반(혹은 1/정수배)으로 줄어드는 데 이런 경우가 여기에 해당합니다. 즉, 관측데이타를 선형(x)으로 줄여 갈 수록 오차는 1/e^x곡선을 따라 줄어듭니다. 삼체문제와 같은 Chaos세계에서는 오차를 반으로 줄이기 위해서는 그에 배로 증가하는 관찰데이타가 필요합니다. 예를 들면 오차를 1/2로 줄이기 위해서는 데이타가 2배가 필요하고 1/4로 줄이기 위해서는 4배가 필요한 식입니다. 여기서 사용된 수치는 설명을 위해 제가 임의로 정한수이고 실제로 이 수치는 Chaos의 정도나 그 세계의 복잡도를 수치적으로 말해주는 Fractal 차원과 밀접한 관련이 있습니다. 이러한 세계에서는 오차를 0으로 근사시킬 수록 그를 위해 요구되는 관측 데이타는 무한대로 폭발합니다. 예를 들면 코흐곡선(_/\_ 모양의 선분으로 이뤄진 프랙탈)은 그 프랙탈 차원이 1.2618.. 으로 코흐곡선의 오차를 1/2로 줄이기 위해서는, 코흐곡선을 2배 확대한 그림을 같은 오차로 인식하는 문제로 치환해서 생각하면 됩니다. 이때 필요한 관측데이터가 2^1.2618..= ..(계산기 있는분들 계산좀.. ^^) 개의 관측데이터가 요구됩니다. 만델브로트 곡선은 원처럼 안과 밖이 확실이 구분되는 도형이고 그 안/밖을 구분해주는 선분의 길이는 무한대입니다. 또한 만델브로트의 도형의 외곽선은 그 프랙탈차원이 2차원으로 그 선분은 사실상 2차원상의 도형과 같은 넓이를 갖는 셈입니다 (햐! 신기하죠? ^^). 이 만델브로트 곡선에서 오차를 1/2로 줄이기 위해서는 코흐곡선과 마찬가지로 같은 오차에서 2배확대한 만델브로트 곡선을 인식하는 문제로 치환해서 생각하면, 필요한 관측데이터는 2^2=4배가 됩니다. 이러한 식의 프랙탈과 Chaos의 세계에서는 허용하는 오차를 1/2, 1/4, 1/8 ... 이렇게 줄여가는 순간 2, 2^4, 2^8, ... 이렇게 exponential한 관찰데이타가 필요하게 됩니다. 이는 공학적으로 그리고 실질적으로 계산 불능하다고 이야기합니다.. 이러한 식의 문제는 알고리즘 분야의 NP-complete문제에서도 똑같이 발생합니다. TSP문제는 그 문제를 쪼개서 부분적으로 풀어 합하려는 시도를 하는 순간 그 안에 프랙탈 구조를 가지고 있음을 확인할 수 있습니다. 모든 NP-complete문제는 서로 변환가능하고, 하나가 풀리면 나머지는 동시에 다 풀리는 연관성을 가지고 있습니다. 또한 모든 NP-complete문제들은 프랙탈 구조를 가지고 있습니다. P=NP인지 아닌지를 증명하는 문제가 프랙탈분야의 이론들을 동원하면 증명할 수 있는 방법이 있을 것이라고 저는 확신하고 있습니다. 뭐 대충 모든 NP-complete문제는 프랙탈이다를 증명하고. 프랙탈 구조의 탐색공간을 Polynomial Time을 갖는 알고리즘으로는 탐색이 불가능하다는 것을 보이면 될 것으로 생각합니다. 만약 Polynomial알고리즘으로 탐색이 가능하면 역으로 그 알고리듬으로 탐색공간을 만들어내면 프랙탈이 생성되어야 되는데 이는 프랙탈 정의에서 보면 논리의 모순이죠? 어 증명되어따? O.O 누구 알고리즘 분야에 있는 사람 이 문제좀 빨랑 풀어주세요... 그리고 기본 아이디어는 쇼팽이란 사람이 제시했다는걸 논문에 쓰는 걸 잊지 마시고 ^^ 자 이제 다시 삼체문제와 같은 Chaos의 세계로 되돌아가서 공학적인 관점에서 이 문제가 왜 공학적으로 근사하는 방식으로 푸는 방법이 계산불능상태에 빠지는 지는 이런 관점에서 설명하게 되면 다음과 같이 바꿔표현할 수 있습니다. "오차를 줄여감에 따라 필요한 관찰데이타가 exponential하게 증가한다" 앞으로 어떤 모델이 계산불능상태에 빠진다는 이야기는 위의 문장을 포함하는 논리로 생각하시면 됩니다. __ 쇼팽 |