클레이 수학 7대 난제 .. 1. P vs NP Problem
1. P vs NP Problem (P 대 NP 문제)
이 문제는 밀레니엄 문제들 중에서 유일하게 컴퓨터와 관련된 문제이다. 많은 사람들은 이를 의아하게 여길 것이다. “요새는 수학 연구를 대부분 컴퓨터로 하잖아?”라고 반문할 것이다. 정말 그렇까? 아니다. 실상은 그렇지 않다. 물론 맞는 말이기도 하다. 대부분의 수치 계산은 컴퓨터에 의해서 수행된다.
그러나 수치 계산은 수학의 작은 부분에 불과하며 핵심적인 부분이 아니다. 전자 컴퓨터는 수학에서 나왔지만 - 컴퓨터를 위해서 위해서 필요한 수학의 마지막 단계는 최초의 컴퓨터가 제작되기 수년 전인 1930년대에 완성되었다 - 지금까지 컴퓨터 세계에서 발생한 중요한 - 세상에서 가장 중요하다고 인정할만한 - 수학적 문제는 단 두 개에 불과하다. 그 두 문제는 계산기계라기보다는 개념적 처리과정으로 이해된 컴퓨터와 관련된다.
물론 이런 이해가 실제 계산에 대해서 중요한 함축을 가질 가능성은 열려 있다. 두 문제 중 하나는 헬베르트의 1900년 문제 목록에 들어있다. 그 문제 - 특성한 방정식들은 컴퓨터로 풀 수 없음을 증명하라는 문제 - 는 1970년에 해결되었다.
다른 한 문제는 더 최근에 제기되었다. 그 문제는 컴퓨터가 얼마나 계산과제들을 효율적으로 해결할 수 있는지와 관련된다. 컴퓨터 과학자들은 계산과제들을 두 개의 주요 범위로 분류한다. P형 과제는 컴퓨터를 통해서 효율적으로 해결할 수 있다.
E형 과제는 컴퓨터로 완수할려면 100만년 이상이 걸릴 수도 있다. 안타깝게도 공업이나 상업에서 발생하는 주요 계산과제들은 대부분 세번째 문제인 NP형에 속한다.NP형은 P형과 E형의 중간인 것처럼 보인다. 정말 그럴까? NP형 과제가 실은 변형된 P형 과제인 것은 아닐까? 대부분의 전문가들은 NP와 P가 다르다고 믿는다. (즉, NP형 계산과제는 P형 계산과제와 다르다고 믿는거죠).
그러나 30년에 걸친 노력에도 불구하고 NP가 P와 같은지 여부는 증명되지 않았다. 이 문제의 해결은 공업, 상업, 그리고 인터넷을 비롯한 전자통신에 커다란 영향을 끼칠 것이다.
- 다음 페이지에서 계속 -
