La complejidad no tan compleja

Estaba viendo con mi hija Sara un video de Derivando, el canal de Youtube del, a mi juicio, excelente divulgador español Eduardo Sáenz de Cabezón. El video estaba dedicado a explicar, de la manera más simple posible, el asunto del problema P vs. NP, incluido entre los 7 problemas del milenio, cuya resolución premiará con 1 millón de dólares (para cada uno) el Instituto Clay de Matemáticas.

He visto todos los videos del canal de Youtube de Eduardo, en los que ha tratado temas que van desde historia de las matemáticas, pasando por topología, probabilidad, análisis y el infaltable número Pi, por poner algunos ejemplos; en todos ellos, casi sin excepción, él logra fácilmente explicar en unos pocos minutos, de una manera amena y clara, los temas abordados, de tal forma que hasta el más lego de los espectadores podría entender, unas veces más, unas veces menos, de lo que se está hablando.

Sin embargo, en el video que estuve viendo con Sara, el del problema P vs. NP, se puede notar que hacer la explicación le ha costado un buen trabajo. Casi, casi no parece un video de divulgación, sino una clase de matemáticas sobre la teoría de la complejidad. Pero no me malentiendan: esto no es una crítica al trabajo de divulgación que Eduardo ha hecho con respecto a este problema, sino una observación sobre la dificultad inherente del asunto que se ha metido a explicar.

Por esa razón, se me ocurrió escribir esta entrada con el fin de abundar sobre algunas ideas presentadas por Eduardo en su video y sobre otras relacionadas con la complejidad.

Lo primero que hay que advertir es que hoy en día la relación entre matemáticas y computación es tal que se ha perdido la línea divisoria entre estas dos ramas del conocimiento humano; antes, un matemático era concebido, más o menos, como una persona que trabajaba con papel y lápiz o tablero y tiza, conjeturando y demostrando “a mano” relaciones entre las formas y las cantidades, pero hoy en día es cada vez más usual que los matemáticos sean excelentes en computación: modelación, simulación, programación…,  lo que les permite abordar una diversidad mayor de problemas, tanto teóricos como aplicados, de una manera diferente: más ágil y, a mi gusto, igual de rigurosa.

Este hecho ha producido una nueva necesidad: reconocer cuál es la mejor solución entre las múltiples formas computacionales de resolver un problema, medida en términos de su coste computacional, es decir de la cantidad de tiempo y de memoria que se usa en su resolución. Este es uno de los objetivos de la teoría de la complejidad. Así, un mismo problema puede tener varias formas de solución, pero una de ellas será la mejor porque utiliza menos tiempo y menos cantidad de recursos computacionales para su procesamiento.

Alguien ajeno al campo podría pensar que este objetivo de la teoría de la complejidad no pasa más que por ser una curiosidad matemática, sin embargo hoy en día es de extrema importancia porque es aplicable a múltiples campos, como lo dice, por ejemplo, la web del  Departamento de Computación de la Universidad de Buenos Aires,  cuando enuncia las aplicaciones de la teoría de la complejidad: “Teoría general de grafos, optimización lineal y no-lineal, local y global, algoritmos on-line, Knowledge Management, microeconomía y algorítmica de publicidad on-line, complejidad de Kolmogorov y azar, algoritmos para problemas de palabras (stringology) con aplicaciones en genómica, álgebra lineal numérica, sampling, teoría de números efectiva, criptografía, constraint data bases, geometría algebraica, semialgebraica y diofántica efectiva (Computer Algebra), teoría algebraica de la complejidad”. Traduciendo e interpretando un poquito, podría decirse que la teoría de la complejidad se puede aplicar a problemas en la economía, la política, la sociología, la genética, la mecánica celeste, la biología, el manejo del conocimiento, por mencionar sólo algunos campos.

En el vídeo, Eduardo habla de los problemas de tipo P y dice que son aquellos que se pueden solucionar en un tiempo razonable; un tiempo razonable es conocido como un tiempo polinomial, es decir cuando el aumento constante en la complejidad del problema, hace aumentar el tiempo y los recursos para su solución en forma de una relación polinomial: al cuadrado, al cubo, etc.  En cambio, en los problemas de tipo NP no se conoce una solución que se produzca en un tiempo razonable, es decir que su mejor solución es de tiempo exponencial, así el aumento constante de la complejidad del problema hace que el tiempo para su resolución se aumente exponencialmente; dentro de estos problemas está el famoso problema del viajante y uno muy importante, la búsqueda de la clave de un criptosistema, o sea un sistema de claves para acceder a información.

Entonces aún no sabemos si P=NP, lo cual es un problema, pero nos permite seguir utilizando los métodos actuales de criptografía para codificar información. En el momento (si llegara algún día) en que demostremos que P=NP, las consecuencias para los sistemas de información serían catastróficas: nadie tendría ninguna parte de su información segura a los ojos de otra persona. Pero así como resolver el problema de que P=NP traería consecuencias adversas, también traería grandes beneficios porque implicaría que todos los problemas de alta complejidad: problemas logísticos, en la salud, en la biología, etc., cuya solución haría que el mundo fuera un lugar mejor, podrían ser resueltos en tiempos razonables, es decir en tiempos polinomiales.

Por último, les dejó el enlace a un excelente escrito de Marta Macho, sobre un libro, de Robin Cousin, en forma de cómic que trata acerca del problema de P=NP: “El investigador fantasma”: https://culturacientifica.com/2017/04/12/investigador-fantasma-pnp/

Carlos Alberto Díez Fonnegra

Decano de la Facultad de Matemáticas e Ingenierías, Konrad Lorenz Fundación Universitaria