| Semana |
Día I |
Día II |
| | |
| I |
Presentación. Máquinas de Turing (MT). Ejemplos.
Lenguajes reconocibles y decidibles. |
Variantes. MT con movimientos {L,R,S}. Múltiples cintas:
simulación y penalización. No determinismo: simulación. |
| II |
MT multidimensionales. Enumeradores. Codificación de problemas.
Problemas decidibles sobre LR: ADFA, ANFA,
AREX, EDFA y EQDFA. Problemas
decidibles sobre lenguajes libres de contexto: ACFG y
ECFG. |
Problema ATM de aceptacióm para MTs.
Conjuntos numerables. Diagonalización.
Indecidibilidad de ATM. Un lenguaje no reconocible. |
| III |
Problemas indecidibles: HALTTM, ETM, REGULARTM y
EQTM. Historias de computación. Lenguajes ALBA y
ELBA. |
Problema PCP: MPCP y PCP. |
| IV |
Reducción de mapeo ≤m. Teoremas sobre reducciones.
Problema EQTM no es reconocible ni co-reconocible. |
Oráculos. Reducción de Turing ≤T. Complejidad en tiempo.
Notaciones asintóticas. Penalización simulación de MT
multicintas y no determinismo. Clase TIME(t(n)). |
| V |
Clase P. Ejemplos: PATH, RELPRIMES, PRIMES, CFLG.
Clase NP: HAMPATH, COMPOSITES. Verificadores. |
MTND para HAMPATH. Relación entre verificadores
y MTNDs. Clase NTIME(t(n)). Caracterización de NP
en función de NTIME. Ej: CLIQUE y SUBSET-SUM.
P vs. NP. Reducciones polinomiales ≤p. |
| VI |
3SAT ≤p CLIQUE. Definición NP-C. SAT es NP-C. |
Problemas NP-C: 3SAT, CLIQUE, VERTEX-COVER. |
| VII |
Problemas NP-C: HAMPATH, UHAMPATH, SUBSET-SUM. |
Complejidad en Espacio. Teorema de Savitch.
Clase PSPACE. Completitud para PSPACE. |
| VIII |
Problemas PSPACE-C: TQBF, FORMULA-GAME y GG. |
Clases L y NL. Completitud. PATH. Transductores.
Completitud en NL. PATH es NL-Completo. NL = CoNL. |
| IX |
Teoremas de jerarquía en espacio y tiempo. Aplicaciones. |
EXPSPACE. Completitud. EQREXE es EXPSPACE-Completo. |
| X |
Relativización. Separación de P y NP con oráculos.
Complejidad de circuitos. |
Relación entre TIME(t(n)) y complejidad en tamaño de circuitos.
CIRCUIT-SAT es NP-Completo. 3SAT es NP-Completo. |
| XI |
Algoritmos probabilísticos. Clase BPP. Amplificación de
la probabilidad. Read-once branching programs (ROBPs). |
EQROBP pertenece a BPP. Introducción a IPS. |
| XII |
Examen. |
|