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 las instancias no tienen un " certificado " de longitud polinomial 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 una máquina de Turing M acotada en el tiempo polinomial tal que para cada instancia x , x es una no -instancia si y solo si: para algunos posible certificado c de longitud acotada por p(n) , 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 de sí para el problema NP original se convierte en una instancia de no para su complemento, y viceversa.
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 de no es lo mismo que para una instancia de 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 un sí-la instancia del problema complementario sería igual de compleja que la no -instancia del problema original de satisfacibilidad NP. [ aclaración necesaria ]
Un problema L es co-NP-completo si y solo si L está en co-NP y para cualquier problema en co-NP, existe una reducción de tiempo polinomial de ese problema a L.