사실 8월 8일자 소식인데요. PGR에는 아직 올라오지 않은 것 같아 올려봅니다. (관련 전공자들이 특히 PGR에 많으신 것으로 아는데요. 허허)
링크는 여기입니다: http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
HP의 한 연구원이 P와 NP가 서로 다름을 증명했다고 하는 소식입니다.
통계 물리를 사용해 증명했다고 하는데 아직 Correctness는 정확히 검증되지 않은 상태인 것 같습니다.. 만 대단하긴 합니다.
논문이 무척 길다고 하지만 관심 있으신 분들은 읽어보세요.


참고로 모르시는 분들을 위해. P=NP란 수학 7대 난제 중 하나로, P나 NP라 함은 (주로 컴퓨터 상에서) 어떤 문제를 풀기 위해서 알고리즘을 세웠을 때 그 알고리즘이 시간에 대해 복잡한 정도를 나타내는 척도 정도입니다. 정확한 분류는 아니지만 P 문제는 '쉬운 문제', NP 문제는 '어려운 문제'라고 보시면 됩니다.

P가 NP의 부분집합임은 확실하고, P가 NP와 같냐 아니냐(즉 NP이면서 P가 아닌 문제가 존재하느냐)가 그동안 많은 수학자나 전산학자들의 관심사였는데요. 특이하게도 NP 문제중 NP-complete라고 하는 문제들 중 하나만 다항 시간 내에 푸는 알고리즘을 만들더라도 모든 NP 문제가 그 방법을 응용해서 풀리게 됩니다. 그러면 P=NP임이 증명되는 것이고, 반대로 그런 알고리즘이 존재할 수 없음을 보이면 P != NP 임을 증명한 셈이 되겠지요.

사실 P != NP이다!가 더 많은 사람들이 믿는 가설이기는 합니다. 지금껏 많은 사람들이 이를 증명하기 위해 시도해 왔지만 제대로 증명한 사람은 한 명도 없었지요. 전북대학교 김 양곤 교수가 이를 해결했다고 몇 차례 주장한 적이 있으나 학계에서는 인정하지 않고 있고요. 이번에는 어떨지 궁금해집니다. 만약 맞다면, 세계의 난제가 또 하나 풀리는 셈입니다.

(참고 http://ko.wikipedia.org/wiki/P-NP_%EB%AC%B8%EC%A0%9C)