비결정성 알고리즘 썸네일형 리스트형 P vs NP (1) 0. 서론 2003년 12월 국내 한 수학 교수가 'P : NP 문제'를 해결했다고 하여 신문에 크게 난 적이 있다. 이것은 지난 2000년 미국 클레이 수학재단이 한 문제에 100만 달러씩 걸고 발표한 7가지 난제 중 첫 번째 것으로, 현대 컴퓨터 과학의 미해결 문제 중에서 가장 중요한 것으로 손꼽히고 있다. 몇 년을 두고 그에 대한 검증을 한다고 기사에 나왔는데 현재 어떻게 되었는지는 모르겠다. 당시 기사를 읽고 던진 물음이 "P : NP 문제가 도대체 무엇인가?"였다. 페르마의 마지막 정리, 골드바흐의 추측, 사색문제 등이 일반인도 쉽게 이해할 수 있는 난제인데 반하여, P : NP 문제는 그것이 어떤 문제인지 이해하는 데만 해도 알아야 할 배경 지식이 만만치 않게 많다. 이 컨텐츠는 P : NP .. 더보기 이전 1 다음
