Complement of NP (coNP) The complement complexity class of NP. Known relationships If NP = coNP, then any inconsistent Boolean formula of size n has a proof of inconsistency of size polynomial in n.