coNP

NP 문제에서 「예」와 「아니오」를 맞바꾼 문제들의 모임이다. 「이 논리식은 어떤 값을 넣어도 참인가(항진식인가)」가 대표적인데, 「아니오」의 증거(거짓이 되는 값 하나)는 짧지만 「예」의 짧은 증거는 알려져 있지 않다. P ⊆ NP ∩ coNP 이고, NP = coNP 인지는 미해결이다. P = NP 이면 NP = coNP 이므로, NP ≠ coNP 를 증명하면 P ≠ NP 도 따라 나온다. 증명 복잡도는 이 길로 접근하는 분야다.