NP-intermediate
NP 에 있지만 P 도 아니고 NP-완전도 아닌 문제
래드너는 1975년에 P ≠ NP 라면 P 에도 속하지 않고 NP-완전도 아닌 NP 문제가 반드시 있음을 증명했다. 그의 예는 증명을 위해 인위적으로 만든 문제다. 자연스러운 후보로는 인수분해(의 결정 문제 판)와 그래프 동형이 꼽힌다. 다만 어떤 문제가 정말 NP-중간임을 증명하면 P ≠ NP 도 증명되는 셈이므로, 확정된 예는 아직 없다.