Diferencia entre revisiones de «NP-hard»
Contenido eliminado Contenido añadido
m robot Añadido: pt:NP-difícil, fa:انپی سخت Eliminado: zh:NP-hard (deleted) |
Sin resumen de edición |
||
Línea 16:
* 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.
| |||