Teoría de la Complejidad Computacional
Máster Universitario en Matemáticas
(Curso 2025-2026)
- Fundamentos y límites de la computación
- Variantes de máquinas de Turing y su poder computacional
- Máquinas alternantes
- Máquinas no deterministas con restricciones estructurales
- Máquinas de Turing con colas, cintas múltiples, máquinas de Turing en tiempo real
- Máquinas con oráculos
- Jerarquías de complejidad
- Teoremas de jerarquía y refinamientos modernos
- Condiciones débiles para colapsos de jerarquías
- Jerarquía polinomial y jerarquía exponencial
- Complejidad de circuitos
- Clases AC0, ACC0, TC0, NC
- Cotas inferiores (Furst-Saxe-Sipser, Razborov-Smolensky...)
- Minimum Circuit Size Problem
- Barreras de demostraciones naturales (natural proofs)
- Tesis de Razborov-Rudich
- Conexiones entre complejidad de circuitos y el problema P vs NP
- Complejidad de comunicación
- Protocolos deterministas, aleatorios, cuánticos
- Conexiones con estructuras algebraicas
- Complejidad de comunicación multiparte
- Relación con clases como P, NP, BPP, MA, AM
- Límites inferiores y métodos clásicos
- Complejidad y lógica
- Complejidad descriptiva
- Teorema de Fagin
- ASIGNADO: Jobián Gutiérrez Romero
- Lógicas que caracterizan P, NP, PSPACE
- Clases de complejidad relacionadas: FO, MSO, LFP, IFP
- Métodos de demostración de inexpresabilidad
- Relación entre FPC, circuitos y programación lineal
- Límites superiores e inferiores de FPC
- Sistemas proposicionales de prueba
- Sistemas Frege y extended Frege
- Resolución
- ASIGNADO: Isabel Borrego Caraballo
- Interpolación de Craig
- Automatizabilidad
- CDCL solvers
- Aritmética acotada (S12, T21...)
- Funciones NP totales
- Traducciones de Cook, de Paris-Wilkie
- Complejidad en teoría de grafos
- Ancho de árbol y variantes
- Degeneración y aciclicidad
- Algoritmos FPT clásicos
- Kernelización
- W[1], W[2], AW[*]
- ASIGNADO: Pedro José Muñoz Méndez
- Problemas NP-completos y más allá
- Reducciones y dureza de aproximación
- Reducciones AP
- Teorema PCP clásico
- Umbrales de aproximación
- Reducciones polinómicas clásicas
- ASIGNADO: Jerónimo Crespo Almagro
- Reducciones many-one y Turing
- Complejidad parametrizada
- Algoritmos FPT
- Kernelización positiva y negativa
- Jerarquía W
- Reducciones parametrizadas
- Clases XP y variantes
- Constraint Satisfaction Problem
- Problemas CSP sobre dominios finitos
- Simetrías y teoría de clones
- CSP dichotomy theorem (Bulatov-Zhuk)
- Promise CSP
- Problemas de coloración aproximada
- Interpretaciones mediante polimorfismos
- Otras clases de complejidad
- Por debajo de P
- Clases de complejidad: AC0, ACC0, TC0
- NC1, NC
- SC
- L, NL
- Por encima de NP
- Clases co-NP, DP, PH (jerarquía polinomial)
- Σkp, Πkp, colapsos, separaciones condicionales
- #P, PP, ⊕P
- PSPACE, EXP, EXPSPACE, jerarquía exponencial, clases por encima de EXP
- Resultados clásicos: el Teorema de Toda
- Complejidad de cuantificadores alternantes
- Enfoques modernos
- Complejidad cuántica
- Clases de complejidad cuánticas: BQP, QMA, QIP
- Quantum communication complexity
- Quantum walks
- Barreras y límites inferiores
- Complejidad probabilística
- Clases de complejidad probabilísticas: RP, BPP, ZPP
- ASIGNADO: Andrés Luna Barranco
- Pseudoaleatoriedad
- Lemas de amplificación
- Relación entre aleatoriedad y determinismo
- Complejidad dinámica
- Modelos DYNFO
- Algoritmos incrementales
- Data streams
- Relaciones con estructuras de datos
- Autómatas avanzados (en árboles, reversibles, algebraicos)
- Autómatas en árboles
- Autómatas reversibles
- Autómatas algebraicos
- Conexiones con álgebra y lógica
- Algebraic & Geometric Complexity Theory
- Complejidad de circuitos aritméticos
- Strassen's degree bound
- Diferenciación automática
- Conexiones con Deep Learning
- Conjetura VP vs VNP
- Interpretación como problema de orbit closures
- Teoría de representaciones
- ASIGNADO: Raúl Jurado Rodríguez
- Criptografía y complejidad computacional
- Fundamentos de criptografía
- Funciones unidireccionales
- Generadores pseudoaleatorios
- Hard-core predicates
- Criptografía y clases de complejidad
- Relación con NP, co-NP
- Clases probabilísticas: BPP, RP, ZPP
- Clases interactivas: IP, AM, MA
- Supuestos de dureza y separaciones condicionales
- Criptografía basada en retículos
- Problemas SVP y CVP
- Complejidad de aproximación
- Aplicaciones criptográficas
- Criptografía y computación cuántica
- Algoritmos cuánticos y ruptura de esquemas clásicos
- Criptografía post-cuántica
- Pruebas interactivas y zero-knowledge
- Zero-knowledge proofs
- Relación IP = PSPACE
- Protocolos interactivos
- Computación no convencional
- Sistemas P con membranas
- Membranas activas
- A modo de tejidos
- A modo de neuronas
- Computación química y bioinspirada
- Computación con ADN
- Chemical Reaction Networks
- Hybrid networks of evolutionary processors
- Autómatas celulares abstractos
- Tile assembly/Self-assembly
- Modelo de azulejos de Wang
- Ensamblaje determinista y estocástico
- Complejidad geométrica
- Population protocols
- Agentes con memoria constante
- ASIGNADO: Constantino Benjumea Bellott
- Lenguajes semilineales
- Relación con redes biológicas
- Computación reversible
- Máquinas de Turing reversibles
- Construcciones de Bennett
- Computación y termodinámica, límites físicos de la computación
Las presentaciones se realizarán en el seminario H1.50 (Seminario Alejandro Fernández Margarit) en la E. T. S. I. Informática
| Hora |
12 de febrero |
| 8:00 - 9:00 |
Constantino Benjumea |
| 9:00 - 10:00 |
Raúl Jurado |
| 10:00 - 11:00 |
Jerónimo Crespo |
| 11:00 - 12:00 |
Pedro Muñoz |
| 12:00 - 13:00 |
Isabel Borrego |
| 13:00 - 14:00 |
Jobián Gutiérrez |