P와 NP 외에도 두 가지 종류가 더 있습니다.
• NP-완전(NP-complete) 문제: NP-완전 문제는 NP 문제 중에서도 가장 어려운 문제들로 구성된 하위 집합입니다. NP-완전 문제는 다음과 같은 두 가지 조건을 만족해야 합니다.
– 해결책을 생성할 수 있는 알려진 다항시간 알고리즘이 존재하지 않습니다.
– 제안된 해결책이 최적이라는 것을 검증할 수 있는 알려진 다항시간 알고리즘이 존재합니다.
• NP-난해(NP-hard) 문제: NP-난해 문제는 NP 집합에 있는 문제만큼 풀기 어렵지만 NP 집합에는 속하지 않는 문제들을 지칭합니다.
지금까지 소개한 네 종류의 문제를 도식화하면 다음과 같습니다.
▲ 그림 4-3 문제의 네 가지 유형
P = NP가 성립하는지는 여전히 밝혀지지 않았습니다. 수많은 연구자가 이를 규명하기 위해 노력하고 있지만 그 반대인 P ≠ NP일 확률이 매우 높습니다. 그러한 경우 NP-완전 문제를 풀 수 있는 다항시간 알고리즘은 존재하지 않습니다.