Diferencia entre revisiones de «NP-hard»

[[Archivo:P np np-completo np-hard.svg|thumb|300px|right|[[Diagrama de Euler]] de las familias de problemas [[P (clase de complejidad)|P]], [[NP (Complejidad computacional)|NP]], [[NP-completo]], y NP-hard.]]En [[complejidad computacional|teoría de la complejidad computacional]], la [[clase de complejidad]] '''NP-hard''' (o '''NP-complejo''', o ''NP-difícil'') es el conjunto de los [[problema de decisión|problemas de decisión]] que contiene los problemas ''H'' tales que todo problema ''L'' en [[NP (Complejidadclase computacionalde complejidad)|NP]] puede ser [[transformación polinomial|transformado polinomialmente]] en ''H''. Esta clase puede ser descrita como aquella que contiene a los problemas de decisión que son como mínimo tan difíciles como un problema de '''NP'''. Esta afirmación se justifica porque si podemos encontrar un [[algoritmo]] ''A'' que resuelve uno de los problemas ''H'' de NP-hard en [[tiempo polinómico]], entonces es posible construir un algoritmo que trabaje en tiempo polinómico para cualquier problema de [[NP (Complejidad computacional)|NP]] ejecutando primero la reducción de este problema en ''H'' y luego ejecutando el algoritmo ''A''.