Diferencia entre revisiones de «NP-hard»

1 byte añadido ,  hace 7 años
sin resumen de edición
m (Moviendo 13 enlace(s) interlingüístico(s), ahora proporcionado(s) por Wikidata en la página d:q1137554.)
Sin resumen de edición
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 quequé ser un [[problema de decisión]].
 
* Los problemas [[NP-completo]]s 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 decisión [[NP-completo]]s a un problema [[NP-completo]] ''L'' por [[transformación polinómica|transformaciones polinómicas]], y de ''L'' a ''H'' por reducción polinómica de Turing.
Usuario anónimo