Escucha este artículo
Audio generado con IA de Google
0:00
/
0:00
La ciencia computacional teórica (TCS, por sus siglas en inglés) estudia el poder y los retos de la computación mediante dos subdisciplinas: el diseño de algoritmos, para resolver problemas computacionales; y la complejidad computacional, que muestra las limitaciones inherentes a la eficiencia de esos algoritmos. (Lea La ciencia floja que daña el análisis de la pandemia)
Las estructuras discretas, como los grafos, las cadenas y las permutaciones, son fundamentales para la TCS, que se relaciona así estrechamente con las matemáticas. Ambos campos se benefician mutuamente. Las aplicaciones, los conceptos y las técnicas del primero han abierto nuevas investigaciones y han resuelto importantes problemas abiertos en las matemáticas puras y aplicadas.
En este contexto, el matemático húngaro László Lovász (Budapest, 1948) y el israelí Avi Wigderson (Haifa, 1956), que han liderado esos desarrollos en las últimas décadas, son los ganadores del Premio Abel de este año, considerado el ‘Nobel de las matemáticas’.
Lo ha anunciado hoy la Academia Noruega de Ciencias y Letras, quien premia “sus contribuciones fundacionales a la ciencia computacional teórica y a la matemática discreta, y por su papel destacado en la configuración de éstas como campos centrales de la matemática moderna”.
Los trabajos de los galardonados se entrelazan de muchas maneras y, en particular, ambos han hecho contribuciones fundamentales para entender la aleatoriedad en la computación y para explorar los límites de la computación eficiente.
Avances en criptografía
Junto con Arjen Lenstra y Hendrik Lenstra, László, vinculado a la Universidad Eötvös Loránd de Budapest (Hungría), ha desarrollado el llamado algoritmo de reducción de la base de celosía LLL (Lenstra–Lenstra–Lovás), una de las herramientas favoritas de los criptoanalistas, ya que es capaz de romper con éxito varios criptosistemas propuestos.
El análisis de este algoritmo también se utiliza para diseñar y garantizar la seguridad de criptosistemas más recientes, basados en celosías, que parecen resistir los ataques incluso de los ordenadores cuánticos. Es tan solo una de las aportaciones del matemático húngaro, que también ha ayudado a resolver diversos problemas matemáticos relacionados con grafos y del ámbito de la combinatoria.
Por su parte, Avi Wigderson, investigador del Instituto de Estudios Avanzados de Princeton, ha realizado importantes contribuciones a todos los aspectos de la complejidad computacional, especialmente al papel de la aleatoriedad en la computación. Un algoritmo aleatorio es aquel que ‘lanza monedas’ para calcular una solución que es correcta con alta probabilidad.
Los trabajos de Wigderson han permitido construir generadores pseudoaleatorios que convierten unos pocos bits verdaderamente aleatorios en muchos bits pseudoaleatorios. Se trata de ‘extractores’ de bits aleatorios casi perfectos de una fuente imperfecta de aleatoriedad o de determinados grafos.
Junto a otros autores, también ha aportado avances en aspectos tan diversos como el desarrollado de un método para navegar por ‘laberintos’ teniendo en cuenta los puntos de intersección, o sobre los límites inferiores de la eficiencia en protocolos de comunicación y circuitos.
Gracias al liderazgo de Lovász y Wigderson, la matemática discreta y el campo relativamente joven de la ciencia computacional teórica se han establecido como áreas centrales de la matemática moderna.