co-NP-completo

En la teoría de la complejidad , los problemas computacionales co-NP-completos son aquellos que constituyen los problemas más difíciles dentro de 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 una sobrecarga de tiempo polinomial. Si P es diferente de co-NP, entonces no todos los problemas co-NP-completos son resolubles en tiempo polinomial. Si existe una forma de resolver rápidamente un problema co-NP-completo, entonces ese algoritmo puede utilizarse para resolver rápidamente todos los problemas co-NP.

Este concepto resulta de particular interés en el estudio del problema P=NP y en la NP-completitud. Consulte los artículos sobre co-NP y NP-completitud para obtener más detalles.

Un problema de decisión C es co-NP-completo si pertenece a co-NP y si todo problema en co-NP es reducible a él mediante la operación muchos a uno en tiempo polinomial . ^{[ 1 ]} Esto significa que para cada problema L de co-NP , existe un algoritmo de 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 de tiempo polinomial para C , podríamos resolver todos los problemas de co-NP en tiempo polinomial.

El concepto de co-NP-completitud no se distingue particularmente del concepto de NP-completitud, ya que todo problema NP se puede convertir fácilmente en un problema co-NP y viceversa, invirtiendo los términos "aceptar" y "rechazar". En consecuencia, todo problema NP-completo se puede convertir en un problema co-NP-completo.

Esto no significa, sin embargo, que el concepto de co-NP-completitud sea inútil, ya que es posible que exista un problema que sea NP pero no co-NP. Invertir las etiquetas "aceptar" y "rechazar" da como resultado un problema que es co-NP pero no NP. Es un problema abierto si NP=co-NP. Dado que el problema de P=NP también es abierto, todas las instancias conocidas de problemas en${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$están atascados en P.

Un ejemplo de problema co-NP-completo es la comprobación de tautologías , el problema de determinar si una fórmula booleana dada es una tautología; es decir, si toda asignación posible de valores verdadero/falso a variables produce una afirmación verdadera. Esto es complementario al problema de satisfacibilidad booleana , que pregunta si existe al menos una de esas asignaciones, y es NP-completo. ^{[ 1 ]} En más detalle:

• Dada una fórmula, si no es una tautología, entonces puede refutarse en tiempo polinomial mediante una asignación explícita.
• Dada una fórmula, si es satisfacible, entonces se puede demostrar en tiempo polinomial mediante una asignación explícita.

Si algún lenguaje disperso es co-NP-completo (o incluso simplemente co-NP-difícil), entonces P = NP . ^{[ 2 ]} Este resultado se utiliza en el teorema de Mahaney . ^{[ 3 ]}

• Complexity Zoo : coNPC