El Premio Abel reconoce las relaciones de la matemática discreta con las ciencias de la computación

El matemático Lázló Lovász y el informático teórico Avi Widgerson son los galardonados del premio Abel 2021 por “sus contribuciones fundamentales a la informática teórica y las matemáticas discretas, así como su destacado papel para convertirlas en campos centrales de las matemáticas modernas”. Ambos han trabajado en una de las estructuras discretas más populares, los grafos, y sus resultados se aplican en diferentes contextos de la criptografía.

Widgerson (1956) creció en la costera ciudad israelí de Haifa, en una familia judía de origen polaco que sobrevivió al holocausto nazi. En 1983, obtuvo su doctorado en el área de la complejidad computacional en la universidad de Princeton y, desde entonces, su carrera ha sido meteórica. El premio Abel es el último de una larga lista de reconocimientos a los influyentes, innovadores y profundos trabajos de Widgerson en la fundamentación de la informática teórica. Entre ellos, el premio Nevanlinna, el premio Gödel y el premio Knuth.

Por su parte, Lovász (Budapest, 1948) fue un niño prodigio de las matemáticas –ganó tres medallas de oro en las olimpiadas matemáticas internacionales, en dos ocasiones con un reconocimiento especial del jurado–, dentro de una generación de oro de jóvenes matemáticos brillantes, estimulados por el ambiente científico único de la Budapest de postguerra. Entre las influencias del joven Lovász, destaca al mítico y errante matemático Pául Erdős, con quién estableció una colaboración muy fructífera desde su adolescencia. Del mismo modo que Widgerson, el premio Abel es el colofón a una serie de reconocimientos: los premios Gödel y Knuth, así como el premio Wolf, el premio Kyoto y el premio Hipatia de Barcelona.

Los objetos de interés de ambos investigadores son las estructuras discretas. Estas son, por ejemplo, los conjuntos finitos, los números enteros, las fórmulas lógicas o los algoritmos

Los objetos de interés de ambos investigadores son las estructuras discretas. Estas son, por ejemplo, los conjuntos finitos, los números enteros, las fórmulas lógicas o los algoritmos; en contraposición, la función temperatura de una habitación, la curvatura del ala de un avión, en donde la variación se da de manera suave para puntos cercanos, son estructuras continuas. En definitiva, las estructuras discretas son objetos matemáticos que pueden dividirse en partes bien delimitadas. El ejemplo por excelencia son los grafos: objetos formados por conjuntos de puntos y relaciones entre ellos –llamados vértices y aristas, respectivamente–. Los grafos sirven para modelar, por ejemplo, la red de metro de una ciudad o las relaciones entre individuos en una red social; en este segundo caso, el grafo subyacente se construye tomando como vértices las personas y dos personas estarán conectadas mediante una arista si se conocen.

Lovász ha iniciado muchas de las teorías de este campo de investigación y ha obtenido importantes resultados. Entre ellos, ha demostrado conjeturas abiertas, como la llamada conjetura de Kneser, formulada en el año 1955, o la escurridiza conjetura de los grafos perfectos. También ha abierto campos completamente inexplorados: la optimización discreta, la teoría de emparejamientos en grafos o el algoritmo LLL, resultado que hoy en día es fundamental en toda la teoría de criptografía post-cuántica. En los últimos años, Lovász ha sido uno de los máximos desarrolladores de la teoría de grafos límite, una teoría unificadora que intenta mezclar la matemática discreta y los objetos continuos.

Widgerson también ha trabajado con grafos, en concreto, en resultados de complejidad. Dada una estructura discreta muy grande –por ejemplo, pensemos en el grafo asociado a alguna de las redes sociales tan populares hoy en día–, y una propiedad que queramos estudiar –por ejemplo, la aparición de comunidades muy conectadas, que serían grupos de vértices entrelazados con muchas aristas, los denominados clústers. ¿Podemos inventar un mecanismo que compruebe esa propiedad, de forma eficiente?

Este problema de decisión –únicamente nos interesa saber si se puede o no– es extremadamente difícil –y costoso en tiempo– si el grafo es grande. En este sentido, la teoría de la complejidad busca algoritmos que funcionen mejor que los ya conocidos y/o demostrar formalmente que no se puede mejorar la eficiencia de un algoritmo dado. Posiblemente el problema estrella de este campo es el famoso P=NP, uno de los siete problemas del milenio, y sobre el que Widgerson ha realizado contribuciones fundacionales que han dado lugar a la teoría de complejidad tal y como la conocemos hoy.

En cierto modo, la teoría de complejidad ha crecido alrededor Widgerson en los últimos 40 años. Pero además, Widgerson ha contribuído de manera decisiva en muchas otras direcciones: es uno de los investigadores de referencia en las llamadas pruebas de conocimiento cero, y fue el creador del llamado producto zig-zag para la construcción de grafos expansores –que son grafos muy bien conectados, pero a la vez con muy pocas aristas; estas estructuras ya fueron objeto de estudio de los anteriores galardonados con el premio Abel, en parte por su conexión con otras ramas de las matemáticas como la teoría de grupos.

Los dos galardonados coinciden en el uso de ideas probabilísticas muy novedosas que permiten obtener resultados que, de manera determinista sería imposible. Así, Lovász inventó el denominado lema local, que permite demostrar la existencia de objetos combinatorios que, de otra forma, sería impensable encontrar. Y, por su parte, Widgerson ha realizado contribuciones esenciales en el uso de la probabilidad para encontrar algoritmos eficientes que mejoran cualquier algoritmo determinista.

El reconocimiento del trabajo de toda una vida de Lovász y Widgerson confirma, una vez más, el papel fundamental de la matemática discreta, de las ciencias de la computación y de su interacción en el desarrollo de las matemáticas contemporáneas

Juanjo Rué es investigador del Departamento de Matemáticas y del Instituto de Matemáticas (ImTech) de la Universitat Politècnica de Catalunya, y miembro investigador del Centre de Recerca Matemàtica (CRM) y de la Barcelona Graduate School of Mathematics (BGSMath)

Café y Teoremas es una sección dedicada a las matemáticas y al entorno en el que se crean, coordinado por el Instituto de Ciencias Matemáticas (ICMAT), en la que los investigadores y miembros del centro describen los últimos avances de esta disciplina, comparten puntos de encuentro entre las matemáticas y otras expresiones sociales y culturales y recuerdan a quienes marcaron su desarrollo y supieron transformar café en teoremas. El nombre evoca la definición del matemático húngaro Alfred Rényi: “Un matemático es una máquina que transforma café en teoremas”.

Traducción, edición y coordinación: Ágata A. Timón García-Longoria (ICMAT)

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aquí para recibir nuestra newsletter semanal.