Utilizamos cookies propias y de terceros para mejorar nuestros servicios y facilitarte el uso de la web mediante el análisis de tus preferencias de navegación. También compartimos la información sobre el tráfico por nuestra web a los medios sociales y de publicidad con los que colaboramos. Si continúas navegando, consideramos que aceptas nuestra Política de cookies .

19 de Marzo de 2021
Matemáticas

Dos pioneros que conectaron las matemáticas y la computación ganan el premio Abel

Avi Wigderson y László Lovász han recibido el galardón por sus respectivos trabajos en la teoría de la complejidad y la teoría de grafos, y por vincular ambos campos.

De izquierda a derecha, Avi Wigderson y László Lovász, recientes ganadores del premio Abel de 2021. [Cliff Moore, Instituto de Estudios Avanzados (izquierda); Academia Húngara de Ciencias (derecha)]

Cuando Avi Wigderson y László Lovász comenzaron sus carreras, allá por la década de 1970, la informática teórica y las matemáticas puras eran disciplinas casi totalmente independientes. Hoy en día, se han acercado tanto que resulta difícil distinguir la línea que las separa. Por sus numerosas contribuciones fundamentales a ambos campos y por su trabajo para unirlos, Lovász y Wigderson acaban de recibir el premio Abel, un galardón que concede la Academia Noruega de Ciencias y Letras, y que se considera uno de los mayores honores en matemáticas.

«En muchos sentidos, su trabajo es complementario. Avi se dedica a la computación y Lovász a las matemáticas, pero muchos de los temas que investigan están relacionados», subraya Russell Impagliazzo, científico computacional de la Universidad de California en San Diego que ha colaborado con ambos investigadores.

Ese vínculo surgió como resultado del singular periodo que atravesaba la ciencia cuando ambos crecieron.

Wigderson nació en Haifa en 1956. Durante su adolescencia, los científicos computacionales empezaban a esbozar un marco teórico básico que acabaría absorbiendo gran parte de su vida profesional. Ese marco, denominado teoría de la complejidad, consiste en clasificar los problemas computacionales en función de lo difícil que resulta resolverlos mediante algoritmos. La dificultad se mide principalmente en función del número de pasos computacionales, y la distinción más básica es entre problemas «fáciles» y «difíciles».

Un ejemplo de un problema computacional fácil es multiplicar dos números. No importa cómo de grandes sean, los ordenadores pueden calcular su producto rápidamente. Este problema pertenece a la clase de complejidad denominada «P», donde se encuadran todos los problemas computacionales fáciles de resolver.

En cambio, encontrar los factores primos de un número es un problema computacional que parece difícil. No se conoce ningún algoritmo que pueda hacerlo deprisa para cualquier número. Pero si alguien nos da los factores primos de un número, resulta sencillo comprobar que son los factores correctos multiplicándolos entre sí. Este problema pertenece a la clase de complejidad «NP», que comprende los problemas computacionales que pueden ser difíciles de resolver, pero cuyas respuestas son fáciles de verificar.

A principios de los años 1970, los científicos computacionales formularon la principal conjetura del campo de la complejidad computacional, al preguntarse si los problemas de la clase P se corresponden exactamente con los de la NP.

Esta cuestión aún era reciente en 1977, cuando Wigderson ingresó en el Technion, el Instituto Tecnológico de Israel. En las décadas siguientes, el científico haría muchas contribuciones fundamentales a la teoría de la complejidad, ayudando a dilucidar qué problemas y en qué circunstancias, se enmarcan en cada clase de complejidad.

«Cuando empecé el doctorado, la complejidad computacional estaba madurando como campo científico. Yo mismo me desarrollé con ella», asegura Wigderson.

A finales de la década de 1980, Wigderson y su colaborador Ran Raz estudiaron la complejidad computacional del problema del emparejamiento (o «apareamiento») perfecto, una cuestión que también aparece en el trabajo de Lovász. Supongamos que tenemos 20 máquinas, cada una de las cuales es capaz de realizar algunas (pero no todas) de entre 20 tareas distintas. El problema del emparejamiento perfecto consiste en saber si podemos asignar las tareas a las máquinas de forma que se completen todas las tareas y cada máquina lleve a cabo exactamente una.

Wigderson y Raz estudiaron el problema tras añadir ciertas restricciones: imaginaron que el circuito informático que trabajaba en el problema era capaz de realizar la mayoría de las operaciones computacionales habituales (como «y» y «o»), excepto una crucial: la operación «no».

Sin duda, a los científicos computacionales les encantaría poder demostrar sin reservas que un determinado problema computacional es difícil. Pero hasta ahora no lo han logrado (si no, ya sabríamos si P es igual a NP). Así que, como alternativa, tratan de probar que no existe ningún algoritmo rápido para un problema como el del emparejamiento cuando limitamos tanto los recursos computacionales como el tiempo disponible para resolverlo.

«Nos interesa hallar las limitaciones de los algoritmos, y si no podemos hacerlo en el caso más general, los restringimos, les atamos un brazo a la espalda», explica Wigderson. En 1990, él y Raz demostraron que no hay una manera eficaz de usar muchos ordenadores en paralelo para resolver el problema del emparejamiento en circuitos que carezcan de la operación «no».

Por esa misma época, Wigderson trabajaba en otra cuestión central de la complejidad, acerca de cómo influye la aleatoriedad en la velocidad a la que podemos resolver los problemas computacionales. Desde la década de 1970, los expertos en computación sospechaban que la aleatoriedad suponía una ventaja. Habían descubierto que, si permitimos que un algoritmo tome decisiones «a cara o cruz», puede alcanzar una solución mucho más deprisa en algunos problemas (como comprobar si un número es primo) que si le exigimos que dé cada paso de forma determinista.

«Era una época en la que parecía que se podían hacer muchas más cosas con aleatoriedad que sin ella», rememora Wigderson.

Pero en dos artículos publicados en los años 90, Wigderson y sus colaboradores demostraron que, bajo ciertos supuestos, siempre es posible convertir un algoritmo aleatorio rápido en un algoritmo determinista rápido. Ese resultado estableció que la clase de complejidad conocida como «BPP» (problemas que se pueden resolver rápidamente con algoritmos que incluyen un elemento de aleatoriedad) era exactamente igual a la clase de complejidad P, sirvió para incorporar décadas de trabajo sobre algoritmos aleatorios al cuerpo principal de la teoría de la complejidad y cambió la forma en que los científicos computacionales veían los algoritmos aleatorios.

«Creo que hoy en día casi cualquier científico sostendría que la aleatoriedad no es muy potente porque, bajo supuestos en los que creemos firmemente, podemos eliminarla», asegura Wigderson.

Wigderson, que lleva en el Instituto de Estudios Avanzados desde 1999, ha obtenido muchos otros resultados relacionados con la teoría de la complejidad, incluida una técnica denominada «producto en zigzag» que está directamente relacionada con varias áreas de las matemáticas puras y proporciona una estrategia para escapar de un laberinto registrando solo un número fijo de intersecciones. La amplitud del trabajo de Wigderson refleja el modo en que ha crecido el campo de la complejidad computacional desde que empezó a trabajar en él.

«Avi es una figura esencial en este campo», valora Impagliazzo. «Es una de las personas que lo mantienen cohesionado y que poseen una visión clara a medida que lo desarrollamos.»

Lovász y Wigderson ya se conocían bien; aquí los vemos charlando en Oslo, durante las conferencias del premio Abel de 2012. [<a href="https://owpdb.mfo.de/detail?photo_id=16659" target="_blank">Gert-Martin Greue/Instituto de Investigación Matemática de Oberwolfach</a>]

Mientras Wigderson ampliaba las fronteras de la teoría de la complejidad, Lovász trabajaba en un campo íntimamente relacionado que también tenía mucho margen para crecer.

Nacido en Budapest en 1948, Lovász fue una estrella de las matemáticas desde muy joven. En su adolescencia, ganó tres medallas de oro en la Olimpiada Internacional de Matemáticas y también triunfó en un concurso húngaro que aislaba a los prodigios de las matemáticas en cabinas de cristal y los retaba a resolver problemas.

Al principio de su carrera, Lovász conoció al influyente matemático húngaro Paul Erdős, quien le ayudó a introducirse en el campo de la teoría de grafos. En aquella época, la teoría de grafos era un remanso matemático, conocido por plantear problemas divertidos como la conjetura de los cuatro colores (que ahora es un teorema demostrado), que pregunta si es posible colorear los países de cualquier mapa con solo cuatro colores, sin que haya dos países limítrofes con el mismo color.

«Yo no diría que era desconocida, pero sin duda la teoría de grafos no era la corriente principal de las matemáticas, porque muchos de los problemas o resultados surgían a partir de acertijos o de las matemáticas recreativas», relata Lovász, que ahora trabaja en la Universidad Eötvös Loránd de Hungría. Pero eso ya estaba cambiando cuando Lovász se doctoró en 1970, a la edad de 22 años, y una de las principales razones fue el nacimiento y rápido crecimiento de la ciencia computacional.

Los ordenadores, por fuerza, trabajan con cantidades discretas: cadenas binarias de unos y ceros. La combinatoria es la matemática de los objetos discretos, y uno de sus principales campos es la teoría de grafos, que estudia redes de aristas (líneas) que conectan vértices (puntos). Como tal, proporcionaba una especie de lenguaje para investigar las incipientes cuestiones de la informática teórica.

Lovász considera el desarrollo de los ordenadores y de la teoría de grafos como una feliz concurrencia histórica, y la compara con el modo en que el análisis (una forma avanzada de cálculo) alcanzó la mayoría de edad, más de un siglo antes, a través de la investigación de cuestiones físicas urgentes.

«A veces uso la analogía del análisis y la física de los siglos XVIII y XIX, que crecieron de la mano», ratifica Lovász. «Algo parecido ocurrió con la teoría de grafos y la ciencia computacional.»

Gran parte del trabajo de Lovász se ha centrado en el desarrollo de algoritmos para resolver distintos tipos de problemas. Uno de sus resultados más influyentes fue el algoritmo LLL, llamado así por sus creadores, Lovász y los hermanos Arjen y Hendrik Lenstra.

El algoritmo se refiere a unos objetos geométricos llamados retículos, que son conjuntos de puntos en el espacio cuyas coordenadas suelen tener valores enteros. El algoritmo LLL aborda una cuestión básica sobre sus propiedades: ¿qué punto del retículo es el más próximo al origen? Es una pregunta sencilla que suele ser difícil de contestar, sobre todo en espacios de dimensión alta y cuando los puntos del retículo crean una forma distorsionada.

En lugar de responder a la pregunta de forma exacta, el algoritmo LLL halla una buena aproximación, identificando un punto y garantizando que no hay ningún otro que esté mucho más cerca del origen. Debido a la amplia aplicabilidad de este modelo geométrico, la capacidad de hallar ese punto tiene implicaciones en numerosos ámbitos, desde la factorización de polinomios hasta la verificación de la seguridad de los sistemas criptográficos.

«Es uno de los algoritmos fundamentales. Es importante tanto desde el punto de vista teórico como desde el práctico», afirma Gil Kalai, del Centro Interdisciplinario de Herzliya y la Universidad Hebrea de Jerusalén, que en el pasado formó parte del comité del premio Abel.

Otra de las contribuciones más significativas de Lovász tiene un cariz probabilístico. En la década de 1960, Paul Erdős desarrolló lo que vino a denominarse el «método probabilístico» para responder preguntas sobre grafos. A menudo los matemáticos quieren saber si existe un grafo con una cierta propiedad. Una forma de dilucidarlo es hallar un grafo que la tenga. Pero Erdős se dio cuenta de que otro enfoque consistía simplemente en demostrar que un grafo elegido al azar tendría muchas probabilidades de poseer esa propiedad.

Por desgracia, el método probabilístico de Erdős funcionaba mejor para establecer la existencia de grafos que ya se conocían. En la década de 1970, Lovász colaboró con Erdős para diseñar una técnica complementaria, conocida como el lema local de Lovász, que sirve para demostrar la existencia de grafos muy inusuales. Desde entonces, se ha convertido en una de las técnicas esenciales de este campo.

«Se trata de una herramienta que se ha usado cientos o miles de veces en demostraciones posteriores», apunta Kalai.

A lo largo de su carrera, Lovász ha resuelto muchos otros problemas de la teoría de grafos, entre ellos la conjetura de Kneser (sobre el mínimo número de colores necesarios para colorear un determinado grafo) y una cuestión sobre las condiciones que garantizan los emparejamientos perfectos y otras estructuras afines en los grafos.

También ha planteado varias conjeturas que aún sirven de guía para el campo de la teoría de grafos en la actualidad. Entre ellas cabe destacar dos problemas, la conjetura KLS y la conjetura EFL, para las que no se han obtenido resultados relevantes hasta hace unos meses.

Durante los años en que pioneros como Wigderson perfeccionaban nuestra comprensión de la complejidad computacional, Lovász respondía a preguntas sobre grafos que ayudaban a definir las fronteras entre las distintas clases de complejidad.

«Esos conceptos relacionados con la complejidad se reflejaban en preguntas muy sencillas sobre grafos», concluye Kalai. «Así que las preguntas sobre grafos cobraron mucha importancia, y Lovász las estudió desde el principio.»

Por ello, resulta muy oportuno que dos pioneros que lograron unir sus respectivos campos estén ahora unidos de otra manera: por el Premio Abel.

Kevin Hartnett/Quanta Magazine 

Artículo traducido por Investigación y Ciencia con permiso de QuantaMagazine.org, una publicación independiente promovida por la Fundación Simons para potenciar la comprensión de la ciencia.

Más información en la página web del premio Abel.

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.