Diferencia entre revisiones de «NP-hard»

31 bytes añadidos ,  hace 10 años
m
m (r2.7.3) (Bot Añadido: zh:NP困难)
El [[problema de la suma de subconjuntos]] es un ejemplo de problema NP-hard y se define como sigue: dado un conjunto ''S'' de enteros, ¿existe un subconjunto no vacío de ''S'' cuyos elementos sumen cero?
 
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 transformá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, quedá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 algoritmo asociado pero el [[problema de la parada]] es [[problema indecidible|indecidible]].
 
 
== Convención de nombres que incluyen las siglas NP ==
24 569

ediciones