Co-NP

En teoria de la complexitat computacional, la classe de complexitat co-NP és el conjunt dels problemes de decisió complementaris als de la classe NP. Per problema complementari s'entén aquell que les respostes positiva del qual o negativa estan invertides.

La classe de complexitat P és un subconjunt tant de NP com de co-NP i es pensa que l'inclusió és estricta en abdós casos. Es pensa també que NP i co-NP són diferents. De ser cert açò, cap problema de NP-complet podria estar en co-NP i cap problema de co-NP-complet podria estar en NP.

Açò es demostra com seguix: Si hi haguera un problema en NP-complet i en co-NP al mateix temps, tot problema de NP es reduiria en ell, es deduïx que para tot problema en NP es podria construir una màquina de Turing no determinista que decidira el problema complementari en temps polinòmic, és dir, NP seria un subconjunt de co-NP i, per tant els complements de NP serien subconjunt dels complements de co-NP, és dir, co-NP seria un subconjunt de NP, Per tant NP i co-NP serien el mateix conjunt. De forma simètrica es demostra que cap problema en co-NP-complet pot estar en NP.