En la teoría de la complejidad , los problemas computacionales que son co-NP-completos son aquellos que son los problemas más difíciles en co-NP , en el sentido de que cualquier problema en co-NP puede reformularse como un caso especial de cualquier problema co-NP-completo con solo una sobrecarga polinomial. Si P es diferente de co-NP, entonces todos los problemas de co-NP-completo no se pueden resolver en tiempo polinómico. Si existe una forma de resolver rápidamente un problema de co-NP-completo, entonces ese algoritmo se puede utilizar para resolver rápidamente todos los problemas de co-NP.
Cada problema co-NP-completo es el complemento de un problema NP-completo . Hay algunos problemas tanto en NP como en co-NP , por ejemplo, todos los problemas en P o factorización de enteros . Sin embargo, no se sabe si los conjuntos son iguales, aunque se cree que la desigualdad es más probable. Consulte co-NP y NP-complete para obtener más detalles.
Fortune demostró en 1979 que si algún lenguaje disperso es co-NP-completo (o incluso co-NP-duro), entonces P = NP , [1] una base crítica para el teorema de Mahaney .
Definicion formal
Un problema de decisión C es co-NP-completo si está en co-NP y si cada problema en co-NP es polinomial-tiempo muchos-uno reducible a él. [2] Esto significa que para cada problema de co-NP L , existe un algoritmo de tiempo polinomial que puede transformar cualquier instancia de L en una instancia de C con el mismo valor de verdad . Como consecuencia, si tuviéramos un algoritmo de tiempo polinomial para C , podríamos resolver todos los problemas de co-NP en tiempo polinomial.
Ejemplo
Un ejemplo de un problema de co-NP-completo es la tautología , el problema de determinar si una fórmula booleana dada es una tautología; es decir, si cada posible asignación de valores verdaderos / falsos a las variables produce un enunciado verdadero. Esto está estrechamente relacionado con el problema de satisfacibilidad booleano , que pregunta si existe al menos una asignación de este tipo y es NP-completo. [2]
Referencias
- ^ Fortuna, S. (1979). "Una nota sobre los conjuntos completos dispersos" (PDF) . Revista SIAM de Computación . 8 (3): 431–433. doi : 10.1137 / 0208034 . hdl : 1813/7473 .
- ^ a b Arora, Sanjeev; Barak, Boaz (2009). Teoría de la complejidad: un enfoque moderno . Prensa de la Universidad de Cambridge. ISBN 978-0-521-42426-4.