Problema completo NP

Problema NP-completo : en la teoría de los algoritmos , un problema con la respuesta "sí" o "no" de la clase NP , al que cualquier otro problema de esta clase se puede reducir en tiempo polinomial (es decir, usando operaciones cuyo número no excede algún polinomio dependiendo del tamaño de los datos originales). Por lo tanto, los problemas NP-completos forman, en cierto sentido, un subconjunto de problemas "típicos" en la clase NP: si se encuentra un algoritmo de solución "polinomialmente rápido" para algunos de ellos, entonces se puede resolver cualquier otro problema de la clase NP. igual de “rápidamente””.

Formal definición

Un alfabeto es cualquier conjunto finito de caracteres (por ejemplo, {} o {}). El conjunto de todas las palabras posibles ( cadenas finales compuestas por los caracteres de este alfabeto) sobre algún alfabetose denota. Un idioma sobre un alfabetoes cualquier subconjunto del conjunto, es decir. ${0,1}$ ${a B C}$ $\Sigma$ $\Sigma^{*}$ $L$ $\Sigma$ $\Sigma^{*}$ $L\subconjunto \Sigma ^{*}$

La tarea de reconocimiento de un idioma es la determinación de si una palabra dada pertenece al idioma . $L$ $L$

Sea y sea dos idiomas sobre el alfabeto . Se dice que un lenguaje es reducible (según Karp) a un lenguaje si existe una función , , que es computable en tiempo polinomial y tiene la siguiente propiedad: $L_{1}$ $L_{2}$ $\Sigma$ $L_{1}$ $L_{2}$ $f\dos puntos \Sigma ^{*}\to \Sigma ^{*}$

$x\en L_{1}$ si y solo si . La reducibilidad de Karp se denota como o . $f(x)\en L_{2}$ $L_{1}{\leq}_{p}L_{2}$ $L_{1}\varpropto L_{2}$

Se dice que un idioma es NP-duro si cualquier idioma de la clase NP es reducible a él. Se dice que un lenguaje es NP-completo si es NP-difícil y pertenece a la clase NP. $L_{2}$

Informalmente hablando, el hecho de que el problema se reduzca al problema significa que el problema “no es más difícil” que el problema (porque si podemos resolver , entonces podemos resolver y ). Por lo tanto, la clase de problemas NP-difíciles incluye problemas NP-completos y problemas que son "más difíciles" que ellos (es decir, aquellos problemas a los que se pueden reducir los problemas NP-completos). La clase NP incluye problemas NP-completos y problemas que son "más fáciles" que ellos (es decir, aquellos problemas que se reducen a problemas NP-completos). $A$ $B$ $A$ $B$ $B$ $A$

De la definición se deduce que si se encuentra un algoritmo que resuelve algún (cualquier) problema NP-completo en tiempo polinomial, entonces todos los problemas NP estarán en la clase P , es decir, se resolverán en tiempo polinomial.

NP-completo en sentido fuerte

Una tarea se denomina NP-completa en sentido estricto si tiene una subtarea que:

no es un problema con parámetros numéricos (es decir, el valor máximo de las cantidades encontradas en este problema está acotado desde arriba por un polinomio en la longitud de la entrada)
es NP-completo.

La clase de tales problemas se llama NPCS . Si la hipótesis P ≠ NP es verdadera, entonces no existe un algoritmo pseudopolinomial para el problema NPCS .

Hipótesis P ≠ NP

La cuestión de la coincidencia de las clases P y NP ha sido uno de los problemas centrales abiertos durante más de treinta años . La comunidad científica tiende a dar una respuesta negativa a esta pregunta [1] — en este caso, no será posible resolver problemas NP-completos en tiempo polinomial.

Ejemplos de problemas NP-completos

Véase también

Igualdad de clases P y NP

Notas

↑ Guillermo I. Gasarch. La encuesta P=?NP. (neopr.) // Noticias SIGACT. - 2002. - T. 33 , N º 2 . - S. 34-47 . -doi : 10.1145/ 1052796.1052804 .
↑ Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. Tetris es difícil, incluso aproximado . impresión.

Literatura

Gary M., Johnson D. Máquinas informáticas y problemas difíciles . Archivado el 4 de noviembre de 2019 en Wayback Machine . M.: Mir, 1982.
Thomas H. Kormen y otros Capítulo 34. NP-Completitud // Algoritmos: Construcción y análisis = Introducción a los algoritmos. - 2ª ed. - M. : "Williams" , 2006. - 1296 p. — ISBN 0-07-013151-1 .
John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducción a la teoría de autómatas, lenguajes y computación. - M. : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .

Enlaces

completitud NP
Complejidad computacional de juegos y rompecabezas Archivado el 6 de diciembre de 2006 en Wayback Machine .
Un compendio de problemas de optimización NP. Editores - Pierluigi Crescenzi, Viggo Kann Archivado el 5 de diciembre de 2006 en Wayback Machine .

Clases de complejidad de algoritmos
Considerado ligero	DLOGTIME CA 0 ACC 0 TC0 [ es L SL RL Países Bajos CAROLINA DEL NORTE SC CC PAGS P-completa ZPP PR BPP BQP EQP APX
Se supone que es difícil	UP notario público NP completo co-NP co-NP-completo AM MA QMA PH ⊕P PÁGINAS #PAGS #P- IP ESPACIO P PSPACE-completo
Considerado difícil	EXPTIME NEXPTIME EXPESPACIO 2-EXPTIM PRIMARIA R PR RE RE-completar Co-RE Co-RE-completo TODOS

Problemas NP-completos
Problema de maximización del apilamiento (packing)	Envasado en contenedores embalaje bidimensional embalaje lineal embalaje por peso embalaje por valor El problema de la mochila
teoría de grafos teoría de conjuntos	Problema de cobertura de vértices Haga clic en problema El problema de un conjunto independiente (conjunto) Establecer problema de cobertura Problema de Steiner El problema del viajante de comercio Problema generalizado del viajante de comercio
Problemas algorítmicos	Problema de satisfacibilidad para fórmulas booleanas (en forma normal conjuntiva)
Juegos de lógica y rompecabezas.	Etiquetas generalizadas (juego en N 2 -1) problema de solución más corta Problemas cuyas soluciones se aplican en Tetris Problema de sudoku generalizado Problema de llenado de cuadrados latinos La tarea de Kakuro
Clases de dificultad La investigación de operaciones Mejoramiento optimización combinatoria Matemáticas Aplicadas Teoría de Algoritmos Programación dinámica 21 Problema de Karp NP-completo