En la teoría de la complejidad computacional , co-NP es una clase de complejidad . Un problema de decisión X es miembro de co-NP si y solo si su complemento X está en la clase de complejidad NP . La clase se puede definir de la siguiente manera: un problema de decisión está en co-NP si y solo si para cada no -instancia tenemos un " certificado " de longitud polinómica y hay un algoritmo de tiempo polinómico que se puede usar para verificar cualquier supuesto certificado.
Es decir, co-NP es el conjunto de problemas de decisión donde existe un polinomio y una máquina de Turing M acotada en el tiempo por polinomios tales que para cada instancia x , x es una no -instancia si y solo si: para algún posible certificado c de longitud acotada por , la máquina de Turing M acepta el par ( x , c ) . [1]
Mientras que un problema NP pregunta si una instancia dada es una instancia sí , su complemento pregunta si una instancia es una instancia no , lo que significa que el complemento está en co-NP. Cualquier instancia sí para el problema NP original se convierte en una instancia no para su complemento, y viceversa.
Un ejemplo de un problema NP-completo es el problema de satisfacibilidad booleano : dada una fórmula booleana, ¿es satisfacible (hay una entrada posible para la cual la fórmula dé como resultado verdadero)? El problema complementario pregunta: "dada una fórmula booleana, ¿es insatisfacible (todas las entradas posibles de la fórmula dan como resultado falso)?". Dado que este es el complemento del problema de satisfacibilidad, un certificado para una instancia no es lo mismo que para una instancia sí del problema NP original: un conjunto de asignaciones de variables booleanas que hacen que la fórmula sea verdadera. Por otro lado, un certificado de una instancia sí para el problema complementario (cualquiera que sea la forma que pueda tomar) sería igualmente complejo que para la instancia no del problema de satisfacibilidad NP original.
Un problema L es co-NP-completo si y sólo si L está en co-NP y para cualquier problema en co-NP , existe una reducción en tiempo polinomial de ese problema a L.
Determinar si una fórmula en lógica proposicional es una tautología es co-NP-completo: es decir, si la fórmula se evalúa como verdadera bajo cada posible asignación a sus variables. [1]
P , la clase de problemas resolubles en tiempo polinomial, es un subconjunto tanto de NP como de co-NP. Se piensa que P es un subconjunto estricto en ambos casos. Debido a que P es cerrado bajo complementación, y NP y co-NP son complementarios, no puede ser estricto en un caso y no estricto en el otro: si P es igual a NP, también debe ser igual a co-NP, y viceversa. [2]
También se piensa que NP y co-NP son desiguales. [3] Si es así, entonces ningún problema NP-completo puede estar en co-NP y ningún problema co-NP-completo puede estar en NP. [4] Esto se puede demostrar de la siguiente manera. Supongamos por el bien de la contradicción que existe un problema NP-completo X que está en co-NP. Dado que todos los problemas en NP se pueden reducir a X , se deduce que para cada problema en NP, podemos construir una máquina de Turing no determinista que decide su complemento en tiempo polinomial; es decir, . De esto, se deduce que el conjunto de complementos de los problemas en NP es un subconjunto del conjunto de complementos de los problemas en co-NP; es decir, . Por lo tanto . La prueba de que ningún problema co-NP-completo puede estar en NP si es simétrico.
co-NP es un subconjunto de PH , que a su vez es un subconjunto de PSPACE .
Un ejemplo de un problema que se sabe que pertenece tanto a NP como a co-NP (pero que no se sabe que esté en P) es la factorización de enteros : dados los enteros positivos m y n , determinar si m tiene un factor menor que n y mayor que uno. La pertenencia a NP es clara; si m tiene dicho factor, entonces el factor en sí mismo es un certificado. La pertenencia a co-NP también es sencilla: uno puede simplemente enumerar los factores primos de m , todos mayores o iguales a n , que el verificador puede confirmar como válidos mediante la multiplicación y la prueba de primalidad AKS . Actualmente no se sabe si existe un algoritmo de tiempo polinomial para la factorización, equivalentemente, que la factorización de enteros está en P, y por lo tanto este ejemplo es interesante como uno de los problemas más naturales que se sabe que están en NP y co-NP pero no se sabe que estén en P. [5]
