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.
| Control de autoridades |
|
|---|
Datos: Q955748