Co-NP

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 solo ninguna instancia tiene un polinomio de longitud "certificado" y hay un algoritmo de tiempo polinomial 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 p(n) y un polinomio acotado en el tiempo M tal que para cada instancia x, x es una instancia no si y solo si: para algún posible certificado c de longitud limitada por p(n), la máquina de Turing M acepta el par (x, c).

Problemas complementarios

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 de sí para el problema NP original se convierte en una instancia de no para su complemento, y viceversa.

Insatisfacción

Un ejemplo de un problema NP-completo es el problema booleano de satisfacibilidad: dada una fórmula booleana, ¿es satisfacible (hay una entrada posible para la cual la fórmula da como resultado verdadero)? El problema complementario pregunta: "dada una fórmula booleana, ¿es insatisfactoria (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 el mismo que para una instancia sí del original Problema NP: 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 sería tan complejo como la instancia no del problema original de satisfacibilidad del NP.

Problemas duales

Completitud de Co-NP

Un problema L es co-NP-completo si y solo si L está en co-NP y para cualquier problema en co-NP existe un polinomio- reducción de tiempo 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.

Relación con otras clases

P, la clase de problemas polinómicos que pueden resolverse en tiempo, es un subconjunto tanto de NP como de co-NP. Se piensa que P es un subconjunto estricto en ambos casos (y demostrablemente no puede ser estricto en un caso y no estricto en el otro).

También se cree que NP y co-NP son desiguales. 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. Esto se puede demostrar de la siguiente manera. Supongamos que, en aras de la contradicción, existe un problema NP-completo X que está en co-NP. Dado que todos los problemas en NP se pueden reducir a X, se sigue que para cada problema en NP, podemos construir un 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. Así co-NP = NP. La prueba de que ningún problema 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 pertenece tanto a NP como a co-NP (pero que no se sabe que está en P) es la factorización de enteros: enteros positivos dados m y n, determine 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 mismo es un certificado. La membresía en co-NP también es sencilla: uno puede enumerar los factores primos de m, todos mayores o iguales a n, que el verificador puede confirmar que son 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, de manera equivalente 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 conocido por estar en p