computer science - problems - ¿Los problemas NP-difíciles que no son NP-completos son más difíciles?
problemas np ejemplos (6)
A mi entender, todos los problemas de NP-completo son NP-duros, pero se sabe que algunos problemas de NP-hard no son NP-completos, y los problemas de NP-hard son al menos tan difíciles como los problemas de NP-completos.
¿Eso significa que los problemas NP-difíciles que no son NP-completos son más difíciles? ¿Y cómo es más difícil?
- NP-completo debe ser NP y NP-duro.
- y NP-hard que no son NP-completos no son NP.
- Ahora, por definición de NP, hay alguien que da respuesta a la instancia del problema. y hay verificador para verificar.
- esto significa que NP-Hard no tiene ninguno de ellos. Por eso son difíciles de resolver, es cierto.
De http://en.wikipedia.org/wiki/NP-hard#Examples
También hay problemas de decisión que son NP-difíciles pero no NP-completos, por ejemplo, el problema de la detención. Este es el problema que pregunta "dado un programa y su entrada, ¿se ejecutará para siempre?" Esa es una pregunta de sí / no, por lo que este es un problema de decisión. Es fácil demostrar que el problema de detención es NP-duro pero no NP-completo.
El problema de detención de Turing es indecidible y pertenece a NP-Hard set. Para resolver el problema, no tenemos ningún factor decisivo, ya que es un lenguaje RE. Así que no tenemos ningún algoritmo para resolverlo. Por lo tanto, está claro que los problemas sin solución también se encuentran en el conjunto NP-Hard. Por lo tanto, NP-Hard set también contiene los idiomas o problemas para los que no tenemos ningún algoritmo que resolver.
El problema de la detención de la máquina de Turing es indecidible en las máquinas de Turing y NP-hard, pero no en el NPC. Al parecer es más difícil;)
Para responder a esta pregunta, primero debe comprender qué problemas de NP-hard también son NP-completos. Si un problema de NP-duro pertenece al conjunto NP, entonces es NP-completo. Para pertenecer al conjunto NP, un problema debe ser
(i) un problema de decisión,
(ii) la cantidad de soluciones al problema debe ser finita y cada solución debe ser de longitud polinómica, y
(iii) dada una solución de longitud polinomial, deberíamos poder decir si la respuesta al problema es sí / no
Ahora, es fácil ver que podría haber muchos problemas NP-difíciles que no pertenecen al conjunto NP y son más difíciles de resolver. Como ejemplo intuitivo, la versión de optimización de vendedor ambulante donde necesitamos encontrar un programa real es más difícil que la versión de decisión de vendedor ambulante donde solo necesitamos determinar si existe o no un programa con longitud <= k.