co-NP

En la teoría de la complejidad computacional , co-NP es una clase de complejidad . Un problema de decisión X pertenece a co-NP si y solo si su complemento X pertenece a la clase de complejidad NP . La clase se puede definir de la siguiente manera: un problema de decisión está en co-NP si y solo si para cada instancia de no tenemos un " certificado " de longitud polinómica y existe un algoritmo de tiempo polinómico que se puede utilizar para verificar cualquier supuesto certificado.

Es decir, co-NP es el conjunto de problemas de decisión donde existe un polinomio ⁠ $p(n)$ y una máquina de Turing M con límite de tiempo polinomialtal que para cada instancia x , x es una no- instancia si y solo si: para algún certificado posible c de longitud limitada por $p(n)$ ⁠ , la máquina de Turing M acepta el par $(x, c)$ .^{[ 1 ]}

Problemas complementarios

Mientras que un problema NP pregunta si una instancia dada es una instancia "sí" , su complemento pregunta si una instancia es una instancia "no" , lo que significa que el complemento está en co-NP. Cualquier instancia "sí" para el problema NP original se convierte en una instancia "no" para su complemento, y viceversa.

Insatisfacción

Un ejemplo de problema NP-completo es el problema de satisfacibilidad booleana : dada una fórmula booleana, ¿es satisfacible (existe alguna entrada posible para la cual la fórmula dé como resultado verdadero)? El problema complementario pregunta: "dada una fórmula booleana, ¿es insatisfacible (todas las entradas posibles de la fórmula dan como resultado falso)?". Dado que este es el complemento del problema de satisfacibilidad, un certificado para una instancia negativa es el mismo que para una instancia positiva del problema NP original: un conjunto de asignaciones de variables booleanas que hacen que la fórmula sea verdadera. Por otro lado, un certificado para una instancia positiva del problema complementario (cualquiera que sea su forma) sería igual de complejo que para la instancia negativa del problema de satisfacibilidad NP original.

co-NP-completitud

Un problema L es co-NP-completo si y solo si L está en co-NP y para cualquier problema en co-NP, existe una reducción en tiempo polinomial de ese problema a L.

Reducción de tautología

Determinar si una fórmula en lógica proposicional es una tautología es co-NP-completo: es decir, si la fórmula se evalúa como verdadera bajo cada posible asignación a sus variables. ^{[ 1 ]}

Relación con otras clases

Problema sin resolver en informática

⁠

{\textsf {NP}}\ {\overset {?}{=}}\ {\textsf {co-NP}}

⁠

Más problemas sin resolver en informática

Inclusiones de clases de complejidad que incluyen P , NP , co-NP, BPP , P/poli , PH y PSPACE.

P , la clase de problemas resolubles en tiempo polinomial, es un subconjunto tanto de NP como de co-NP. Se considera que P es un subconjunto estricto en ambos casos. Dado que P es cerrado bajo complementación, y NP y co-NP son complementarios, no puede ser estricto en un caso y no estricto en el otro: si P es igual a NP, también debe ser igual a co-NP, y viceversa. ^{[ 2 ]}

También se piensa que NP y co-NP son desiguales, ^{[ 3 ]} y su igualdad implicaría el colapso de la jerarquía polinómica PH a NP. Si son desiguales, entonces ningún problema NP-completo puede estar en co-NP y ningún problema co-NP-completo puede estar en NP. ^{[ 4 ]} Esto se puede demostrar de la siguiente manera. Supongamos, por contradicción, que existe un problema NP-completo X que está en co-NP. Dado que todos los problemas en NP se pueden reducir a X , se deduce que para cada problema en NP, podemos construir una máquina de Turing no determinista que decide su complemento en tiempo polinomial; es decir , ${\textsf {NP}}\subsetequ {\textsf {co-NP}}$ ⁠ . De esto se deduce que el conjunto de complementos de los problemas en NP es un subconjunto del conjunto de complementos de los problemas en co-NP; es decir, ⁠ ${\textsf {co-NP}}\subsetequ {\textsf {NP}}$ ⁠ . Por lo tanto ⁠ ${\textsf {co-NP}}={\textsf {NP}}$ ⁠ . La prueba de que ningún problema co-NP-completo puede estar en NP si ⁠ ${\textsf {NP}}\neq {\textsf {co-NP}}$ es simétrico.

co-NP es un subconjunto de PH , que a su vez es un subconjunto de PSPACE .

Factorización de enteros

Un ejemplo de un problema que se sabe que pertenece tanto a NP como a co-NP (pero que no se sabe que esté en P) es la factorización de enteros : dados enteros positivos m y n , determinar si m tiene un factor menor que n y mayor que uno. La pertenencia a NP es clara; si m tiene tal factor, entonces el factor en sí mismo es un certificado. La pertenencia a co-NP también es directa: basta con enumerar los factores primos de m , todos mayores o iguales a n , que el verificador puede confirmar como válidos mediante la multiplicación y la prueba de primalidad AKS . Actualmente se desconoce si existe un algoritmo de tiempo polinomial para la factorización, lo que equivale a que la factorización de enteros esté en P, y por lo tanto este ejemplo es interesante como uno de los problemas más naturales que se sabe que están en NP y co-NP, pero que no se sabe que estén en P. ^{[ 5 ]}

Referencias

1 2 Arora, Sanjeev; Barak, Boaz (2009). Teoría de la complejidad: un enfoque moderno . Cambridge University Press. pág. 56. ISBN 978-0-521-42426-4.
↑ Mayordomo, Elvira (2004). "P versus NP" . Monografías de la Real Academia de Ciencias de Zaragoza . 26 : 57-68 .
↑ Hopcroft, John E. (2000). Introducción a la teoría de autómatas, lenguajes y computación (2.ª ed.). Boston: Addison-Wesley. ISBN 0-201-44124-1.Capítulo 11.
↑ Goldreich, Oded (2010). P, NP y NP-completitud: Los fundamentos de la complejidad computacional . Cambridge University Press . pág. 155. ISBN 9781139490092.
↑ Aaronson, Scott (2016). " P ≟ NP " (PDF) . En Nash, John Forbes Jr .; Rassias, Michael Th. (eds.). Problemas abiertos en matemáticas . Springer International Publishing. pp. 1–122 . doi : 10.1007/978-3-319-32162-2_1 . ISBN 9783319321622.Consulte la Sección 2.2.4 Factorización e isomorfismo de grafos, págs. 19-20 del libro (págs. 17-18 de la versión enlazada).

Enlaces externos

Zoológico de la complejidad : coNP

[A&B-1] 1 2 Arora, Sanjeev; Barak, Boaz (2009). Teoría de la complejidad: un enfoque moderno . Cambridge University Press. pág. 56. ISBN 978-0-521-42426-4.

[2] Mayordomo, Elvira (2004). "P versus NP" . Monografías de la Real Academia de Ciencias de Zaragoza . 26 : 57-68 .

[3] Hopcroft, John E. (2000). Introducción a la teoría de autómatas, lenguajes y computación (2.ª ed.). Boston: Addison-Wesley. ISBN 0-201-44124-1.Capítulo 11.

[4] Goldreich, Oded (2010). P, NP y NP-completitud: Los fundamentos de la complejidad computacional . Cambridge University Press . pág. 155. ISBN 9781139490092.

[5] Aaronson, Scott (2016). " P ≟ NP " (PDF) . En Nash, John Forbes Jr .; Rassias, Michael Th. (eds.). Problemas abiertos en matemáticas . Springer International Publishing. pp. 1–122 . doi : 10.1007/978-3-319-32162-2_1 . ISBN 9783319321622.Consulte la Sección 2.2.4 Factorización e isomorfismo de grafos, págs. 19-20 del libro (págs. 17-18 de la versión enlazada).

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]