NP-완전

NP 에 속하면서 NP-난해인 결정 문제다. NP-완전 문제는 서로 다항 시간에 환산되므로 어려움이 모두 같다. 하나라도 다항 시간에 풀리면 P = NP 이고, 하나라도 다항 시간에 풀 수 없음이 증명되면 P ≠ NP 다. 쿡(1971)과 레빈(1973)이 SAT 가 NP-완전임을 보였고, 카프(1972)가 21개 문제를 더했으며, 지금은 수천 가지가 알려져 있다. NP-완전은 최악의 경우에 관한 말이어서, 실제로 만나는 사례는 쉽게 풀리는 일이 많다.