Diferencia entre revisiones de «NP-hard»
Contenido eliminado Contenido añadido
NP-hard = NP-complejo |
m Convención de nombres |
||
Línea 16:
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 parada es indecidible.
== Convención de nombres que incluyen las siglas NP ==
Los nombres de familias de problemas con las siglas NP es algo confusa. Los proplemas '''NP-hard'' no son todos NP, a pesar de que estas siglas aparecen es el nombre de la familia. Sin embargo, los nombres están actualmente muy arraigados y plantear un cambio de nomenclatura resulta poco realista. Por otra parte, las familias de problemas con las siglas NP son todas definidas tomando como referencia la familia [[NP (Complejidad computacional)|NP]]:
:'''NP-completo''' — significa problemas que son ''completos'' en NP, es decir, los más difíciles de resolver en NP;
:'''NP-hard''' — (NP-difícil) quiere decir ''al menos'' tan complejo como NP (pero no necesariamente en NP);
:'''NP-easy''' — (NP-fácil) quiere decir ''a lo sumo'' tan dificil como NP (pero no necesariamente en NP);
:'''NP-equivalente''' — significa igualmente difícil que NP, (pero no necesariamente en NP).
| |||