Saltar al contenido ForoHackers

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

Teoría de la complejidad
#3400 · · Citar · 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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder