section_heading: NP<nowiki> = </nowiki>co-NP
paragraph_text: Gdje je co-NP skup koji sadrži komplementarne probleme (tj. problem s invertiranim da/ne odgovorima) NP problema. Vjeruje se da te dvije klase nisu jednake, iako to dosad nije dokazano. Pokazano je da ako ove dvije klase nisu jednake, da tada slijedi da nijedan NP-potpun problem ne može biti u co-NP i nijedan co-NP-potpun problem ne može biti u NP.