본문 바로가기

계산 이론

P vs NP (2) - 문제의 환원과 NP-완전성으로의 응용 0. 간단한 복습 먼저 P와 NP에 대한 간단한 복습으로부터 시작하자. P 문제는 '결정성 알고리즘으로 다항식 시간 내에 해결 가능한 결정형 문제'이다. '결정성 알고리즘', '다항식 시간', '해결 가능하다', '결정형 문제'와 같은 용어들은 모두 이미 친숙하리라고 가정하고 앞으로 설명할 것이다. P 문제들의 집합을 P 클래스라 한다. NP 문제는 '비결정성 알고리즘으로 다항식 시간 내에 해결 가능한 결정형 문제'이다. P 문제와 다른 점이라면 알고리즘이 결정성이냐 비결정성이냐의 차이이다. NP 문제들을 집합을 NP 클래스라 한다. 결정성 알고리즘은 비결정성 알고리즘에서 비결정도가 1인 특수한 경우이다. 그러므로 P 클래스가 NP 클래스에 포함됨은 명백하다. 역으로 NP클래스가 P클래스에 포함되는지는 .. 더보기
P vs NP (1) 0. 서론 2003년 12월 국내 한 수학 교수가 'P : NP 문제'를 해결했다고 하여 신문에 크게 난 적이 있다. 이것은 지난 2000년 미국 클레이 수학재단이 한 문제에 100만 달러씩 걸고 발표한 7가지 난제 중 첫 번째 것으로, 현대 컴퓨터 과학의 미해결 문제 중에서 가장 중요한 것으로 손꼽히고 있다. 몇 년을 두고 그에 대한 검증을 한다고 기사에 나왔는데 현재 어떻게 되었는지는 모르겠다. 당시 기사를 읽고 던진 물음이 "P : NP 문제가 도대체 무엇인가?"였다. 페르마의 마지막 정리, 골드바흐의 추측, 사색문제 등이 일반인도 쉽게 이해할 수 있는 난제인데 반하여, P : NP 문제는 그것이 어떤 문제인지 이해하는 데만 해도 알아야 할 배경 지식이 만만치 않게 많다. 이 컨텐츠는 P : NP .. 더보기