Demostraciones de Indecidibilidad y Complejidad Computacional: Reducciones y Clases P y NP

Demostración de Indecidibilidad: HALT_TM

Suponemos que INF_TM es decidible. Sea R un decisor para INF_TM. Construimos un decisor S para HALT_TM:

S(<M,w>):

1. Construye una máquina M' que, sobre la entrada x, realiza lo siguiente:
   • a) Simula M sobre w durante x pasos.
   • b) Si M ha parado en esos x pasos, ACCEPT.
   • c) Si M no ha parado en esos x pasos, REJECT.
2. Ejecuta R(<M'>).
3. Si R acepta, ACCEPT.
4. Si R rechaza, REJECT.

Análisis de casos

• Caso 1: M para sobre w. La máquina M' acepta x, por lo que R acepta y S acepta. M' aceptaría en t pasos y existen infinitas cadenas con longitud mayor o igual que t; por tanto, L(M') es infinito.
• Caso 2: M' nunca ve a M parar en x pasos. M' rechaza toda entrada x. L(M') no es infinito. R rechaza y S rechaza.

Como S decidiría HALT_TM, pero HALT_TM es indecidible, llegamos a una contradicción.

Demostración de Indecidibilidad: A_TM

Suponemos, por contradicción, que EMPTY_TM es decidible. Sea R un decisor para EMPTY_TM. Construimos un decisor S para A_TM:

S(<M,w>):

1. Construye una máquina M' que, sobre la entrada x, hace lo siguiente: ignora x, simula M sobre w. Si M acepta w, ACCEPT. Si M rechaza w, REJECT. Si M no para sobre w, no para.
2. Ejecuta R(<M'>).
3. Si R acepta, REJECT.
4. Si R rechaza, ACCEPT.

Análisis de casos

• Caso 1: M acepta w → L(M') = Σ* (no está vacío). Entonces R rechaza y S acepta.
• Caso 2: M no acepta w → L(M') = ∅. Entonces R acepta y S rechaza.

Así, S decidiría A_TM, pero A_TM es indecidible, lo cual genera una contradicción.

Conceptos Fundamentales

• Decidible: Construcción de una máquina que siempre termina. Si la condición se cumple, acepta; si no, rechaza. Al terminar siempre, es decidible.
• P: Se proporciona un algoritmo y se calcula su complejidad. Si es polinómica, el lenguaje pertenece a P.
• NP: Se proporciona un certificado y un verificador. Se demuestra que el verificador opera en tiempo polinómico.
• Reducción desde HALT_TM: Se supone que el lenguaje objetivo es decidible y se usa su decisor para decidir HALT_TM, construyendo una máquina M' que depende de si M para sobre w.
• Reducción desde A_TM: Se supone que el lenguaje objetivo es decidible y se usa su decisor para decidir A_TM, construyendo una máquina M' que depende de si M acepta w.