Co-NP-completo
De Wikipedia, la enciclopedia libre
En teoría de la complejidad computacional, la clase de complejidad co-NP-completo es el conjunto de los problemas de decisión más difíciles de la clase co-NP, en el sentido que son los que menos parecen pertenecer a la clase de complejidad P. De encontrarse una forma de resolver un problema en co-NP-completo en tiempo polinómico, el algoritmo utilizado serviría para resolver todos los problemas de co-NP con la misma complejidad.
Más precisamente, un problema de decisión C pertenece a co-NP-completo si está en co-NP y si todo problema de co-NP tiene una transformación polinómica hacia él. Esto significa que para todo problema L en co-NP, existe un algoritmo que trabaja en tiempo polinómico que puede transformar una instancia de L en una instancia de C con el mismo resultado. Consecuentemente, de tenerse un algoritmo que trabajase en tiempo polinómico para C, se tendría un algoritmo en tiempo polinómico para cada uno de los problemas de co-NP.
Cada problema en co-NP-completo es el complemento de uno en NP-completo. Los dos conjuntos son o iguales o disjuntos. Se supone que es lo último lo que es cierto, pero no se ha demostrado.
| clases de complejidad más importantes |
| L | NL | P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C |
| PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH |
