NP-hard
NP 의 어떤 문제보다도 쉽지 않은 문제
NP 의 모든 문제가 다항 시간에 그 문제로 환산되는 문제를 NP-난해하다고 한다. NP-난해 문제 하나를 다항 시간에 풀면 NP 전체가 다항 시간에 풀린다. NP-난해 문제가 NP 에 속할 필요는 없다. 정지 문제처럼 아예 풀 수 없는 문제도 NP-난해이고, 외판원 문제의 최적 경로 찾기처럼 결정 문제가 아닌 것에도 이 말을 쓴다. NP-난해이면서 NP 에 속하면 NP-완전이다.