Diferencia entre revisiones de «NP-hard»

[[Archivo:P_np_np-completo_np-hard.svg|thumb|300px|right|[[Diagrama de Venn]] 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 (Complejidad computacional)|NP]] puede ser [[transformación polinomial|transformado polinomialmente]] en ''H''. Esta clase puede ser descrita como conteniendo los problemas de decisión que son al menos 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''.

 

Asumiendo que el lenguaje ''L'' es [[NP-completo]],