Co-NP

En teoría de la complejidad computacional, la clase de complejidad co-NP es el conjunto de los problemas de decisión complementarios a los de la clase NP. Por problema complementario se entiende aquel que cuyas respuestas positiva o negativa están invertidas.

La clase de complejidad P es un subconjunto tanto de NP como de co-NP y se piensa que la inclusión es estricta en ambos casos. Se piensa también que NP y co-NP son diferentes. De ser cierto esto, ningún problema de NP-completo podría estar en co-NP y ningún problema de co-NP-completo podría estar en NP.

Esto se demuestra como sigue: Si hubiera un problema en NP-completo y en co-NP al mismo tiempo, todo problema de NP se reduciría en él, se deduce que para todo problema en NP se podría construir una máquina de Turing no-determinista que decidiera el problema complementario en tiempo polinómico, es decir, NP sería un subconjunto de co-NP y, por tanto los complementos de NP serían subconjunto de los complementos de co-NP, es decir, co-NP sería un subconjunto de NP, Por tanto NP y co-NP serían el mismo conjunto. De forma simétrica se demuestra que ningún problema en co-NP-completo puede estar en NP.