Diferencia entre revisiones de «NP-hard»

En [[complejidad computacional|teoría de la complejidad computacional]], la [[clase de complejidad]] '''NP-hard''' 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]] puede ser [[transformación polinomial|transformado polinomialmente]] en ''H''. Esta clase peudepuede ser descrita como conteniendo los problemas de decisión que son al menos tan dificilesdifíciles como un problema de '''NP'''. Esta afirmación se justifica porque si podemos encontrar un [[algoritmo]] ''A'' que resuleveresuelve uno de los problemas ''H'' de NP-hard en [[tiempo polinómico]], entonces es posible construir un algotimoalgoritmo que trabaje en tiempo polinómico para cualquier problema de NP ejecutando primero la reducción de este problema en ''H'' y luego ejecutando el algoritmo ''A''.

Existen problemas NP-hard que no son NP-completos, por ejemplo el [[problema de parada]]. Este problema consiste en tomar un programa y sus datos y decidir si va a terminar o si se ejecutará indefinidamente. Se trata de un problema de decisión y es fácil demostrar que es NP-hard pero no NP-completo. Por ejemplo, el [[problema de satisfacibilidad booleana]] puede reducirse al problema de parada transformandolotransformándolo en la descripción de una máquina de Turing que prueba todos los valores de las variables; cuando encuentra una combinación que satisface la fórmula se detiene y en caso contrario reintenta desde el principio, quedandosequedándose en un lazo infinito. Para ver que el problema de parada no está en NP es suficiente notar que todos los problemas de NP tienen un algorítmoalgoritmo asociado pero el problema de parada es indecidible.