Me ha parecido buenísimo este vídeo que acompaña el artículo de Quanta Magazine titulado Complexity Theory’s 50-Year Journey to the Limits of Knowledge. («Cincuenta años del viaje de la teoría de la complejidad hasta los límites del conocimiento»). Es ameno y directo, con mucha información condensada y una estupenda narración [en inglés, con subtítulos].
Las explicaciones del vídeo resultan muy divulgativas para la complejidad del problema –y nunca mejor dicho– y está ilustrado profusamente con buenos ejemplos. Además, quien aparece explicando detalles es Scott Aaronson, un experto máximo en el tema y creador del Zoo de la complejidad.
En él se aborda el archiconocido problema P versus NP, una cuestión central en complejidad computacional, con intrincadas ramificaciones en el MundoReal™, que busca determinar qué problemas se pueden solucionar en la práctica y cuáles son excesivamente complejos para los ordenadores.
El problema P versus NP sigue 50 años después todavía sin resolver (todavía hay un millón de dólares de premio). La cuestión tiene que ver con la diferencia entre los problemas que se pueden resolver en tiempo polinomial (P), en el que el tiempo requerido depende de una fórmula polinómica como 2n² o 5n³+2n² a diferencia de los que requieren tiempo no-polinómico (ej. 2n) que crecen mucho más rápido. Como ejemplo de NP se habla de un Sudoku: es muy difícil de resolver cuando su tamaño crece pero es muy fácil verificar que la solución es correcta cuando se muestra. Algo similar sucede en criptografía con los números pseudo-primos y los sistemas de clave pública.
Para poder explicarlo bien el vídeo recurre a un repaso rápido pero preciso de la historia de la computación relacionada con este tema: las operaciones lógicas booleanas con transistores, la máquina de Turing y la complejidad de los circuitos lógicos. También habla de la meta-complejidad, que estudia la naturaleza un tanto autorreferencial de las preguntas de complejidad. Por ahí aparecen Turing, Shannon, Von Neumann y muchos otros personajes históricos de primera línea.
Relacionado:
- The Golden Ticket: un libro divulgativo sobre la cuestión P = NP
- The Millennium Problems
- Comprobar si p es primo está realmente en P
- Avances y mejoras tras 44 años en la solución al problema matemático del viajante
- La ameba que resuelve el «problema del viajante» con cierta habilidad y ha sorprendido a los investigadores
- Travelling Salesman, trailer. (O qué sucedería si P=NP)
