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 precisamente si sólo ninguna instancia tiene un " certificado " de longitud polinomial y hay un algoritmo de tiempo polinomial que se puede utilizar para verificar cualquier supuesto certificado.
Es decir, co-NP es el conjunto de problemas de decisión donde existe un polinomio p (n) y una máquina de Turing acotada en tiempo polinomial M tal que para cada instancia x , x es una no- instancia si y solo si: para algunos posible certificado c de longitud acotado por p (n) , la máquina de Turing M acepta el par ( x , c ). [1]
Problemas complementarios
Mientras que un problema de 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 de sí para el problema NP original se convierte en una instancia no para su complemento, y viceversa.
Insatisfacción
Un ejemplo de un problema NP-completo es el problema de satisfacibilidad booleano : dada una fórmula booleana, ¿es satisfactoria (hay una entrada posible para la que la fórmula resulte verdadera)? El problema complementario pregunta: "dada una fórmula booleana, ¿es insatisfactorio (todas las entradas posibles a la fórmula son falsas)?". 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 afirmativa para el problema complementario sería tan complejo como la instancia no del problema de satisfacibilidad NP original. [ aclaración necesaria ]
Problemas duales
co-NP-completitud
Un problema L es co-NP-completo si y sólo si L es en co-NP y para cualquier problema en la co-NP, existe una transformación polinómica de ese problema a L .
Reducción de tautología
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 en todas las asignaciones posibles a sus variables. [1]
Relación con otras clases
P , la clase de problemas polinomiales que se pueden resolver en el tiempo, es un subconjunto de NP y co-NP. Se piensa que P es un subconjunto estricto en ambos casos (y se puede demostrar que no puede ser estricto en un caso y no estricto en el otro). [ cita requerida ]
También se cree que NP y co-NP son desiguales. [2] Si es así, entonces ningún problema de NP-completo puede estar en co-NP y ningún problema de co-NP-completo puede estar en NP. [3] Esto se puede mostrar de la siguiente manera. Supongamos, en aras de la contradicción, que existe un problema NP-completo X que está en co-NP. Dado que todos los problemas en NP pueden reducirse 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, NP ⊆ co-NP. 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, co-NP ⊆ NP. Por tanto, co-NP = NP. La prueba de que ningún problema de co-NP-completo puede estar en NP si NP ≠ co-NP es simétrico.
Factorización de enteros
Un ejemplo de un problema que se sabe que pertenecen a ambos NP y co-NP (pero no se sabe que en P) es factorización de enteros : dado números 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 tal factor, entonces el factor en sí es un certificado. La pertenencia a co-NP también es sencilla: se pueden enumerar los factores primos de m , todos mayores o iguales an , que el verificador puede confirmar que son válidos mediante la multiplicación y la prueba de primalidad de AKS . Actualmente no se sabe si existe un algoritmo de tiempo polinomial para la factorización, lo que equivale a 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 conocen en NP y co-NP pero que no se sabe que estar en P. [ cita requerida ]
Referencias
- ^ a b Arora, Sanjeev; Barak, Boaz (2009). Teoría de la complejidad: un enfoque moderno . Prensa de la Universidad de Cambridge. pag. 56. ISBN 978-0-521-42426-4.
- ^ Hopcroft, John E. (2000). Introducción a la teoría, los lenguajes y la computación de los autómatas (2ª edición) . Boston: Addison-Wesley. ISBN 0-201-44124-1.Cap. 11.
- ^ Goldreich, Oded (2010). P, NP y NP-completitud: los fundamentos de la complejidad computacional . Prensa de la Universidad de Cambridge . pag. 155. ISBN 9781139490092.