Diferencia entre revisiones de «NP-hard»
Contenido eliminado Contenido añadido
m robot Añadido: zh:NP-hard |
Sin resumen de edición |
||
Línea 16:
* 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 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?]].
* Si un problema de optimización ''H'' tiene una versión [[NP-completo|NP-completa]], entonces ''H'' es NP-hard.
| |||