fbpx
Wikipedia

Lista de 21 problemas NP-completos de Karp

Febrero 28, 2022

Por Lista de 21 problemas NP-completos de Karp se entiende a una lista de 21 problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos, y que cumplen la característica en común de que todos ellos pertenecen a la clase de complejidad de los NP-completos. Esta lista fue elaborada en 1972 por el informático teórico Richard Karp, en su trabajo seminal "Reducibility Among Combinatorial Problems" (Reducibilidad entre Problemas Combinatorios),[1]​ como profundización del trabajo de Stephen Cook, quien en 1971 había demostrado uno de los resultados más importantes y pioneros de la complejidad computacional: la NP-completitud del Problema de satisfacibilidad booleana.[2]​

El descubrimiento de Karp de que todos estos importantes problemas eran NP-completos, motivó el estudio de la NP-completitud y de la indagación en la famosa pregunta, de si P = NP.

Los problemas

Mientras que la pertenencia del problema SAT o de satisfacibilidad booleana a la clase de los NP-completos fue demostrada utilizando mecanismos particulares, las pertenencias de los 21 problemas siguientes fueron demostradas mediante reducciones polinomiales. Así, el problema SAT se redujo polinomialmente a los problemas 0-1 INTEGER PROGRAMMING, CLIQUE y 3-SAT, y estos a su vez se redujeron a otros varios. La lista completa es la que se muestra a continuación. Las sangrías denotan el hecho que la NP-completitud del problema fue demostrada por reducción polinomial del problema en el nivel directamente superior. Note que los nombres de los problemas están escritos con letras mayúsculas y corresponden a abreviaciones del nombre en inglés, como es lo usual; junto a ellos, entre paréntesis, se escribe la traducción del nombre en español.

Tras un tiempo se descubrió que muchos de estos problemas podían ser resueltos si su enunciado se particularizaba a unas ciertas clases, o podían ser resueltos aproximadamente con un error máximo de un cierto porcentaje. Sin embargo David Zuckerman demostró en 1996 que cada uno de estos 21 problemas tiene una versión restringida de optimización que es no aproximable a menos que P = NP, demostrando que la versión de la reducción, dada por Karp, generaliza un tipo específico de reducción por aproximación.[3]​

Véase también

Referencias

  1. Richard M. Karp (1972). «Reducibility Among Combinatorial Problems». En R. E. Miller and J. W. Thatcher (editors), ed. Complexity of Computer Computations. New York: Plenum. pp. 85-103. 
  2. Stephen Cook (1971). «The Complexity of Theorem Proving Procedures». Proceedings of the third annual ACM symposium on Theory of computing. pp. 151-158. 
  3. David Zuckerman (1996). «On Unapproximable Versions of NP-Complete Problems». SIAM Journal on Computing 25 (6): 1293-1304. 
  •   Datos: Q1734364

Febrero 28, 2022
lista, problemas, completos, karp, entiende, lista, problemas, computacionales, famosos, tratan, sobre, combinatoria, teoría, grafos, cumplen, característica, común, todos, ellos, pertenecen, clase, complejidad, completos, esta, lista, elaborada, 1972, informá. Por Lista de 21 problemas NP completos de Karp se entiende a una lista de 21 problemas computacionales famosos que tratan sobre combinatoria y teoria de grafos y que cumplen la caracteristica en comun de que todos ellos pertenecen a la clase de complejidad de los NP completos Esta lista fue elaborada en 1972 por el informatico teorico Richard Karp en su trabajo seminal Reducibility Among Combinatorial Problems Reducibilidad entre Problemas Combinatorios 1 como profundizacion del trabajo de Stephen Cook quien en 1971 habia demostrado uno de los resultados mas importantes y pioneros de la complejidad computacional la NP completitud del Problema de satisfacibilidad booleana 2 El descubrimiento de Karp de que todos estos importantes problemas eran NP completos motivo el estudio de la NP completitud y de la indagacion en la famosa pregunta de si P NP Los problemas EditarMientras que la pertenencia del problema SAT o de satisfacibilidad booleana a la clase de los NP completos fue demostrada utilizando mecanismos particulares las pertenencias de los 21 problemas siguientes fueron demostradas mediante reducciones polinomiales Asi el problema SAT se redujo polinomialmente a los problemas 0 1 INTEGER PROGRAMMING CLIQUE y 3 SAT y estos a su vez se redujeron a otros varios La lista completa es la que se muestra a continuacion Las sangrias denotan el hecho que la NP completitud del problema fue demostrada por reduccion polinomial del problema en el nivel directamente superior Note que los nombres de los problemas estan escritos con letras mayusculas y corresponden a abreviaciones del nombre en ingles como es lo usual junto a ellos entre parentesis se escribe la traduccion del nombre en espanol SAT Problema de satisfacibilidad booleana para formulas en forma normal conjuntiva 0 1 INTEGER PROGRAMMING Problema de la programacion lineal entera CLIQUE Problema del clique vease tambien Problema del conjunto independiente SET PACKING Problema del empaquetamiento de conjuntos VERTEX COVER Problema de la cobertura de vertices SET COVERING Problema del conjunto de cobertura FEEDBACK NODE SET FEEDBACK ARC SET DIRECTED HAMILTONIAN CIRCUIT Problema del circuito hamiltoniano dirigido UNDIRECTED HAMILTONIAN CIRCUIT Problema del circuito hamiltoniano no dirigido 3 SAT Problema de satisfacibilidad booleana de 3 variables por clausula CHROMATIC NUMBER Problema de la coloracion de grafos CLIQUE COVER Problema de la cobertura de cliques EXACT COVER Problema de la cobertura exacta HITTING SET STEINER TREE 3 DIMENSIONAL MATCHING Problema del matching tridimensional KNAPSACK Problema de la mochila JOB SEQUENCING Problema de las secuencias de trabajo PARTITION Problema de la particion MAX CUT Problema del corte maximo Tras un tiempo se descubrio que muchos de estos problemas podian ser resueltos si su enunciado se particularizaba a unas ciertas clases o podian ser resueltos aproximadamente con un error maximo de un cierto porcentaje Sin embargo David Zuckerman demostro en 1996 que cada uno de estos 21 problemas tiene una version restringida de optimizacion que es no aproximable a menos que P NP demostrando que la version de la reduccion dada por Karp generaliza un tipo especifico de reduccion por aproximacion 3 Vease tambien EditarComplejidad computacional Lista de problemas NP completosReferencias Editar Richard M Karp 1972 Reducibility Among Combinatorial Problems En R E Miller and J W Thatcher editors ed Complexity of Computer Computations New York Plenum pp 85 103 Stephen Cook 1971 The Complexity of Theorem Proving Procedures Proceedings of the third annual ACM symposium on Theory of computing pp 151 158 David Zuckerman 1996 On Unapproximable Versions of NP Complete Problems SIAM Journal on Computing 25 6 1293 1304 Datos Q1734364 Obtenido de https es wikipedia org w index php title Lista de 21 problemas NP completos de Karp amp oldid 119548454, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos