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 ser reformulado como un caso especial de cualquier problema co-NP-completo con solo una sobrecarga polinómica. Si P es diferente de co-NP, entonces todos los problemas co-NP-completos no son solucionables en tiempo polinómico. Si existe una manera de resolver un problema co-NP-completo rápidamente, entonces ese algoritmo puede usarse 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 que haya desigualdad. Consulte co-NP y NP-completo para obtener más detalles.
Fortune demostró en 1979 que si cualquier lenguaje disperso es co-NP-completo (o incluso sólo 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 polinomialmente reducible a él en tiempo muchos-uno. [2] Esto significa que para cada problema co-NP L , existe un algoritmo en tiempo polinomial que puede transformar cualquier instancia de L en una instancia de C con el mismo valor de verdad . En consecuencia, si tuviéramos un algoritmo en 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 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 de esas asignaciones y es NP-completo. [2]