En 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 sólo sobrecarga polinomial. Si P es diferente de co-NP, entonces todos los problemas co-NP-completos no se pueden resolver en tiempo polinomial. Si existe una manera de resolver rápidamente un problema co-NP-completo, entonces ese algoritmo se puede utilizar para resolver todos los problemas co-NP rápidamente.
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 es más probable la desigualdad. Consulte co-NP y NP-completo para obtener más detalles.
Fortune demostró en 1979 que si cualquier lenguaje escaso es co-NP-completo (o incluso simplemente co-NP-duro), entonces P = NP , [1] una base crítica para el teorema de Mahaney .
Un problema de decisión C es co-NP-completo si está en co-NP y si cada problema en co-NP es reducible en tiempo polinomial muchos uno a él. [2] Esto significa que para cada problema 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 co-NP en tiempo polinomial.
Un ejemplo de un problema co-NP-completo es la tautología , el problema de determinar si una fórmula booleana determinada es una tautología; es decir, si cada posible asignación de valores verdadero/falso a variables produce una afirmación verdadera. Esto está estrechamente relacionado con el problema de satisfacibilidad booleano , que pregunta si existe al menos una asignación de este tipo y si es NP completa. [2]