Skip to the content ForoHackers
Log inJoin

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

Complexity theory
#3400 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply