Complejidad Computacional
| Año | Tercer año |
|---|---|
| Carga horaria | 5 horas semanales |
| Correlativas | Lenguajes Formales, Autómatas y Computabilidad y Técnicas de Diseño de Algoritmos |
Complejidad Computacional es una materia obligatoria de la Licenciatura en Ciencias de la Computación. Su objetivo es definir el concepto de clases de complejidad de problemas computacionales, entendiendo cómo se clasifican los distintos problemas de acuerdo a la cantidad de recursos que consumen.
Programa
Primer parcial (cursada 1C2025): Máquinas de Turing. La clase P. La clase NP. Máquinas no-determinísticas. Reducibilidad polinomial. Teorema de Cook-Levin. Problemas NP-completos. La clase coNP. Las clases EXPTIME y NEXPTIME. La jerarquía de tiempos determinísticos. La jerarquía de tiempos no-determinísticos. Teorema de Ladner. Espacio usado por un cómputo. Espacio polinomial: PSPACE y NPSPACE. Teorema de Savitch.
Segundo parcial (cursada 1C2025): Espacio logarítmico: L y NL. L-reducibilidad. Teorema de Immerman-Szelepcsényi. La jerarquía polinomial. Problemas -completos. Máquinas con oráculo. Teorema de Baker, Gill, Solovay. La jerarquía polinomial y NP con oráculos. Circuitos booleanos. La clase P/poly. El Teorema de Karp-Lipton. Tamaño y profundidad de circuitos. Las clases NCnu y ACnu. Uniformidad: las clases NC y AC. P-completitud.
Parciales
Primeros parciales
| Año | Cuatrimestre | Fecha | Instancia | Links |
|---|---|---|---|---|
| 2025 | Primer cuatrimestre | 14/05/2025 | Parcial | enunciado resuelto |
Segundos parciales
| Año | Cuatrimestre | Fecha | Instancia | Links |
|---|---|---|---|---|
| 2025 | Primer cuatrimestre | 25/06/2025 | Parcial | enunciado |
