Diferencia entre revisiones de «NP-hard»

194 bytes añadidos ,  hace 14 años
sin resumen de edición
Sin resumen de edición
Sin resumen de edición
[[Image: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]],
:2. ∀L' en '''NP''', L' ≤ ''L''
 
En el conjunto NP-Hard se asume que el lenguaje ''L'' satisface la propiedad 2, pero no la la propiedad 1.
 
La clase [[NP-completo]] puede definirse alternativamente como la intersección entre [[NP_(Complejidad_computacional)|NP]] y NP-hard.
 
Algunas consecuencias de la definición son:
 
* Como NP-completo es el tipo más costoso de la clase [[NP_(Complejidad_computacional)|NP]], el problema ''H'' es al menos tan costoso como [[NP_(Complejidad_computacional)|NP]], pero ''H'' no tiene por qué estar en [[NP_(Complejidad_computacional)|NP]] y por tanto no tiene por que ser un [[problema de decisión]].
 
* Los problemas [[NP-completo|NP-completos]] se pueden transformar unos en otros por una reducción polinómica, los problemas NP-completos pueden ser resueltos en tiempo polinómico por reducción a H, así que todos los problemas de NP se reducen a H; sin embargo, esto implica utilizar dos tipos diferentes de transformaciones: de problemas de decision [[NP-completo|NP-completos]] a un problema [[NP-completo]] ''L'' por ||[[transformación polinómica|transofrmaciones polinómicas||]], y de ''L'' a ''H'' por redución polinómica de Turing.
 
* Si hay algún algoritmo para resolver un problema NP-hard, entonces hay algoritmos para resolver todos los problemas de NP en tiempo polinómico, esto significaría que [[Problema ¿P=NP?]].
* Si un problema de optimización ''H'' tiene una versión [[NP-completo|NP-completa]], entonces ''H'' es NP-hard.
 
* Si ''H'' pertenece a [[NP_(Complejidad_computacional)|NP]], entonces ''H'' pertenece también a [[NP-completo]] porque en este caso existe una transormación polinómica de Turing que cumple los requisitos de las transformaciones polinómicas.
 
Un error común es pensar que NP en NP-hard quiere decir no polinómico, ya que aunque hay serias sospechas sobre que no existen algoritmos para resolver estos problemas en tiempo polinómico, esto nunca ha sido demostrado.
24

ediciones