Relación entre NP-problemas difíciles de resolver e indecibles

Question

Estoy un poco confundido acerca de la relación entre problemas indecidibles y problemas difíciles NP. Si los problemas difíciles de NP son un subconjunto de problemas indecidibles, o son los mismos e iguales, o es que no son comparables?

Para mí, he estado discutiendo con mis amigos que los problemas indecidibles son un superconjunto a los problemas difíciles de NP. Existirían algunos problemas que no están en NP duros pero son indecidibles. Pero encuentro que este argumento es débil y estoy un poco confundido. ¿Hay problemas NP-completos que son indecidibles? ¿Hay algún problema en NP duro que sea decidible?

¡Alguna discusión sería de gran ayuda! ¡Gracias!

Answer 1

Indecidible = no se puede resolver para algunas entradas. No importa cuánto tiempo (finito) le dé a su algoritmo, siempre estará mal en alguna entrada.

NP-hard ~ = tiempo de ejecución súper polinomial (suponiendo P! = NP). Eso es ondulado a mano, pero básicamente NP-hard significa que es al menos tan difícil como el problema más difícil en NP.

Ciertamente hay problemas que son NP-hard que no son indecidibles (= son decidibles). Cualquier problema NP-completo sería uno de ellos, digamos SAT.

¿Hay problemas indecidibles que no son NP-hard? No lo creo, pero no es fácil descartarlo: no veo un argumento obvio de que deba haber una reducción del SAT a todos los posibles problemas indecidibles. Podría haber algunos problemas indecibles extraños que no son muy útiles. Pero los problemas estándar indecidibles (el problema de detención, por ejemplo) son NP-duros.

Answer 2

Un NP-hard es un problema que es al menos tan difícil como cualquier problema de NP-complete.

Por lo tanto, un problema indecidible puede ser NP-difícil. Un problema es NP-hard si un oráculo para él haría que resolver problemas NP-complete sea fácil (es decir, solucionable en tiempo polinómico). Podemos imaginar un problema indecidible tal que, dado un oráculo para él, los problemas NP-completos serían fáciles de resolver. Por ejemplo, obviamente cada oráculo que resuelve el problema de detención también puede resolver un problema NP-completo, por lo que cada problema de Turing-complete también es NP-hard en el sentido de que un oráculo (rápido) haría que resolviera NP-completo problemas una brisa.

Por lo tanto, los problemas indecidibles de Turing son un subconjunto de problemas NP-hard.

Answer 3

Problema indefinido, p. Turing Halting Problem es NP-Hard solamente.

    <---------NP Hard------> 
|------------|-------------||-------------|------------|--------> Computational Difficulty 

|<----P--->| 

|<----------NP---------->| 

|<-----------Exponential----------->| 

|<---------------R (Finite Time)---------------->| 

En este diagrama, que muestra pequeño tubo superposición de NP y NP-Hard y que muestra NP-completitud, conjunto es decir, de aquellos problemas que son NP así como NP-Hard.

Los problemas indecidibles son NP Problemas difíciles que no tienen solución y que no están en NP.