CI7541: Teoría de Computación
Blai Bonet |
| Semana | Martes | Jueves |
| I | Presentación. Máquinas de Turing. 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 de lenguajes regulares: ADFA, ANFA, AREX, EDFA, EQDFA. Problemas decidibles de lenguajes libres de contexto: ACFG, ECFG |
Problema ATM de aceptacióm para MTs. Conjuntos numerables. Diagonalización. Indecidibilidad de ATM. Un lenguaje no reconocible. |
| III | Problemas indecidibles de lenguajes: HALTTM, ETM, REGULARTM, EQTM. Historias de computación. Lenguajes: ALBA, 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 de simulaciones 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. Ejemplos: CLIQUE, 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. PSPACE completitud. |
| VIII | Problemas completos para PSPACE: TQBF, FORMULA-GAME, GG. |
Clases L y NL. Completitud. PATH. Transductores. Completitud en NL. PATH es NL-Completo. NL = CoNL. |
| IX | FERIADO. | Teoremas de Jerarquía en espacio y tiempo. Aplicaciones. |
| X | EXPSPACE. Completitud. EQREXE es EXPSPACE-Completo. | Relativización. Separación de P y NP con oráculos. Complejidad de circuitos. |
| XI | Relación entre TIME(t(n)) y complejidad en tamaño de circuitos. CIRCUIT-SAT es NP-Completo. 3SAT es NP-Completo. |
Algoritmos probabilísticos. Clase BPP. Amplificación de la probabilidad. Read-Once Branching Programs. |
| XII | EQROBP pertenece a BPP. Introducción a IPS. | Examen. |