Diferencia entre revisiones de «NP-hard»

5 bytes añadidos ,  hace 11 años
sin resumen de edición
m (robot Añadido: pt:NP-difícil, fa:ان‌پی سخت Eliminado: zh:NP-hard (deleted))
Sin resumen de edició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.
 
* Si hay algún algoritmo polinómico 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?|P=NP]].
 
* Si un problema de optimización ''H'' tiene una versión [[NP-completo|NP-completa]], entonces ''H'' es NP-hard.
Usuario anónimo