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 polinomio sobrecarga. Si P es diferente de co-NP, entonces todos los problemas de co-NP-completo no se pueden resolver en tiempo polinomial. Si existe una manera 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 cualquier lenguaje disperso es co-NP-completo (o incluso 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 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.
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 toda posible asignación de valores verdaderos / falsos a las variables produce una declaració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 es NP-completo. [2]