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 …