La teoría de la complejidad clasifica problemas, no programas, según los recursos que necesita cualquier algoritmo que los resuelva: tiempo, memoria, aleatoriedad, comunicación. Explica por qué unos problemas tienen soluciones rápidas y otros se resisten a todo intento, y sostiene la seguridad de la criptografía moderna.
Conceptos clave
- Problemas de decisión y clases: P se resuelve en tiempo polinómico, NP se comprueba en tiempo polinómico, PSPACE solo necesita memoria polinómica.
- Reducciones: si el problema A se puede transformar en B a bajo coste, B es al menos tan difícil como A.
- NP-completitud: los problemas más difíciles de NP; un algoritmo rápido para uno daría uno para todos.
- Teoremas de jerarquía: con más tiempo o espacio se pueden resolver, demostrablemente, más problemas.
- Más allá del peor caso: aproximación, algoritmos aleatorizados, dificultad en el caso medio y complejidad parametrizada.
Vocabulario
- Tiempo polinómico: tiempo de ejecución acotado por una potencia del tamaño de la entrada, el sentido habitual de «eficiente».
- Certificado: una prueba corta de que una respuesta afirmativa es correcta, que se puede comprobar rápido.
- Oráculo: una caja negra imaginaria que responde una pregunta al instante, usada para comparar clases.
- P frente a NP: la pregunta abierta de si todo problema que se comprueba rápido también se resuelve rápido.
Qué estudiar, en orden
- La notación O grande y la máquina de Turing como modelo de coste.
- Escribe un resolvedor por fuerza bruta y un verificador para un problema como la suma de subconjuntos; compara su crecimiento.
- Aprende las reducciones polinómicas y demuestra una pequeña a mano, como de 3-SAT a clique.
- Lee el teorema de Cook-Levin y entiende por qué SAT es el primer problema NP-completo.
- Repasa las clases de espacio, las aleatorizadas y la aproximación, y asigna tareas reales a una clase.