co-NP problémaosztály

Kapcsolódó fogalmak: 
bonyolultságelmélet
Rövid szöveges bemutatás: 
A bonyolultságelméletben az NP problémák halmazának komplementere a co-NP halmaz. A co-NP halmazba úgy kerülnek problémák, hogy az NP beli döntési problémára felcseréljük az igen-nem válaszokat. Minden NP beli döntési problémának létezik co-NP beli változata.