Los problemas NP-hard que no son NP-completos son más difíciles?

Question

Según entiendo, todos los problemas NP-completos son NP-hard pero se sabe que algunos problemas NP-hard no son NP-completos, y los problemas NP-hard son al menos tan difíciles como los problemas NP-completos.

¿Significa eso que los problemas NP-duros que no son NP-completos son más difíciles? ¿Y cómo es más difícil?

Answer 1

De http://en.wikipedia.org/wiki/NP-hard#Examples

También hay problemas de decisión que son NP-difícil, pero no NP-completo, por ejemplo, el problema de la parada. Este es el problema que pregunta "dado un programa y su entrada, ¿funcionará para siempre?" Esa es una pregunta sí/no, entonces este es un problema de decisión. Es fácil probar que el problema de detención es NP-duro pero no NP-completo.

Answer 2

El conjunto de problemas NP-hard es un superconjunto del conjunto de problemas de NP-complete. Hay clases de complejidad más "difíciles" que NP, por ejemplo PSPACE, EXPTIME o EXPSPACE, y todas ellas contienen problemas NP-hard pero no NP-complete.

Answer 3

Para responder a esta pregunta, primero debe comprender qué problemas NP-hard también son NP-completos. Si un problema NP-duro pertenece al conjunto NP, entonces es NP-completo. Para pertenecer a establecer NP, un problema necesita ser

(i) un problema de decisión,
(ii) el número de soluciones al problema debe ser finito y cada solución debe ser de longitud polinomio, y
(iii) dada una solución de longitud polinómica, deberíamos poder decir si la respuesta al problema es sí/no

Ahora, es fácil ver que podría haber muchos problemas NP-hard que no pertenecen al conjunto NP y son más difíciles de resolver. Como ejemplo intuitivo, la versión de optimización del vendedor ambulante donde necesitamos encontrar un cronograma real es más difícil que la versión de decisión del vendedor ambulante, donde solo tenemos que determinar si existe un cronograma con longitud < = k o no.

Answer 4

El problema de detención de la máquina Turing es indecidible en máquinas Turing y NP-hard, pero no NPC. Aparentemente es más difícil;)

Answer 5

El problema de detención de Turing es indecidible y pertenece al conjunto NP-Hard. Para evitar el problema de detención, no tenemos ningún decisor, ya que es un lenguaje RE. Entonces no tenemos ningún algoritmo para resolverlo. Por lo tanto, está claro que los problemas irresolubles también están en el conjunto NP-Hard. Entonces NP-Hard set también contiene los lenguajes o problemas para los cuales no tenemos ningún algoritmo para resolver.

Answer 6

1. NP-complete debe ser NP y NP-hard.
2. y NP-hard que no son NP-completos no son NP.
3. Ahora, por definición de NP, hay alguien que da una instancia de respuesta para el problema. y hay verificador para verificar.
4. esto significa que NP-Hard no tiene ninguno de ellos. Por lo tanto, son difíciles de resolver es cierto.