Saltar al contenido ForoHackers

Teoría de la complejidad: por dónde empezar

Teoría de la complejidad
#894 · Ophuscado · · Denunciar

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

  1. La notación O grande y la máquina de Turing como modelo de coste.
  2. Escribe un resolvedor por fuerza bruta y un verificador para un problema como la suma de subconjuntos; compara su crecimiento.
  3. Aprende las reducciones polinómicas y demuestra una pequeña a mano, como de 3-SAT a clique.
  4. Lee el teorema de Cook-Levin y entiende por qué SAT es el primer problema NP-completo.
  5. Repasa las clases de espacio, las aleatorizadas y la aproximación, y asigna tareas reales a una clase.

Etiquetas relacionadas

#algorithms #computability #cryptography #formal-methods

Inicia sesión o únete para responder.