다항식 시간 환원 썸네일형 리스트형 P vs NP (2) - 문제의 환원과 NP-완전성으로의 응용 0. 간단한 복습 먼저 P와 NP에 대한 간단한 복습으로부터 시작하자. P 문제는 '결정성 알고리즘으로 다항식 시간 내에 해결 가능한 결정형 문제'이다. '결정성 알고리즘', '다항식 시간', '해결 가능하다', '결정형 문제'와 같은 용어들은 모두 이미 친숙하리라고 가정하고 앞으로 설명할 것이다. P 문제들의 집합을 P 클래스라 한다. NP 문제는 '비결정성 알고리즘으로 다항식 시간 내에 해결 가능한 결정형 문제'이다. P 문제와 다른 점이라면 알고리즘이 결정성이냐 비결정성이냐의 차이이다. NP 문제들을 집합을 NP 클래스라 한다. 결정성 알고리즘은 비결정성 알고리즘에서 비결정도가 1인 특수한 경우이다. 그러므로 P 클래스가 NP 클래스에 포함됨은 명백하다. 역으로 NP클래스가 P클래스에 포함되는지는 .. 더보기 이전 1 다음
