Lungo le stesse linee, il co-NP è la classe che contiene i problemi del complemento (vale a dire problemi con le risposte sì/no invertite) di problemi NP. Si ritiene che NP non sia uguale al co-NP, ma non è stato ancora dimostrato. È stato dimostrato che se queste due classi di complessità non sono uguali allora P non è uguale a NP. co-NP.
In quale classe di complessità completano i problemi di NP?
co-NP co-NP