theory - problemas - ¿Prueba de que el problema de la detención es NP-duro?

p=np

Question

En esta respuesta a una pregunta sobre las definiciones de NP, NP-hard y NP-complete, Jason afirma que

El problema de la detención es el clásico problema NP-difícil. Este es el problema que dado un programa P y entrada I, ¿se detendrá? Este es un problema de decisión, pero no está en NP. Está claro que cualquier problema de NP-completo se puede reducir a este.

Si bien estoy de acuerdo en que el problema de la detención es intuitivamente un problema mucho más "difícil" que cualquier otro en NP, honestamente no puedo ofrecer una prueba matemática formal de que el problema de la detención es NP difícil. En particular, parece que no puedo encontrar un mapeo polinomial de muchos a uno de instancias de cada problema en NP (o al menos, cualquier problema conocido de NP-completo) sobre el problema de detención.

¿Hay una prueba directa de que el problema de la detención es NP-duro?

Answer 1

Comenzamos notando que todos los problemas NP-completos son reducibles a 3SAT. Ahora tenemos una máquina de Turing que recorre todas las asignaciones posibles, y si no se encuentra una asignación satisfactoria, se ejecuta para siempre. Esta máquina se detiene solo si la instancia de 3SAT es satisfactoria.

Completando la prueba, podemos, en tiempo polinomial, reducir cualquier instancia de un problema NP-completo a 3SAT. A partir de ahí, podemos reducir este problema a una instancia del problema de detención al vincular la entrada con una descripción de la máquina de Turing descrita anteriormente (que tiene un tamaño constante). Este emparejamiento se puede hacer en tiempo polinomial, porque la máquina de Turing solo tiene un tamaño constante. Luego, el problema NP-completo original tiene respuesta "sí" si la instancia de 3SAT es satisfactoria si la máquina de Turing se detiene en la entrada dada.