Avi Wigderson y László Lovász recibieron este prestigioso premio por su trabajo en el desarrollo de la teoría de la complejidad y la teoría de grafos, y por combinar estos dos campos.
Cuando Avi Wigderson y László Lovász comenzaron su carrera en los años 70, la informática teórica y las matemáticas puras eran dos materias completamente diferentes. Pero hoy están tan cerca que es difícil discernir una frontera entre ellos.
Los dos científicos han recibido el Premio Abel por sus contribuciones fundamentales a ambos campos y por acercar las disciplinas. El premio lo concede la Academia Noruega de Ciencia y Literatura y está considerado como uno de los más altos honores en matemáticas.
«En muchos sentidos, su trabajo es complementario. Avi trabaja en el campo de la informática, mientras que Lovász es matemático. Pero muchos de los temas que tratan están relacionados», afirma el informático Russell Impagliazzo, de la Universidad de California en San Diego.
¿Pueden las máquinas hacer arte?
Todo el mundo esta seguro de que lo único a lo que le sacamos ventaja a las maquinas es en nuestra parte creativa, el arte era una capacidad que tan solo el ser humano tenia y por lo tanto era inaccesible para las máquinas. Pero en esta nueva década 2020 La aparición y evolución de la Inteligencia Artificial obliga a replantearse si el tema artístico, ya sea pintar, componer o escribir sigue siendo patrimonio exclusivo de la humanidad. El debate está abierto y promete ser interesante.
Quien sabe. quizas llega el día en el que el ser humano compra robot para que le pinte un cuadro, ahora mismo ya los tenemos cocinandonos la cena.
Una medida de la dificultad
Wigderson nació en Haifa, Israel, en 1956. Cuando era adolescente, los informáticos estaban empezando a desarrollar un marco teórico que influiría en gran parte de su futura vida profesional.
En este marco, la teoría de la complejidad, los problemas informáticos se clasifican según su dificultad para resolverlos con algoritmos. La principal medida es el número de pasos computacionales necesarios. La distinción más fundamental es: ¿simple o complicado?
Un ejemplo de problema computacional sencillo es la multiplicación de dos números:
Independientemente del tamaño de los valores, los ordenadores pueden determinar rápidamente el producto. Por lo tanto, la tarea pertenece a la clase de complejidad P, que contiene todos los problemas computacionales fácilmente resolubles.
Por otro lado, la factorización de números primos parece pertenecer a los problemas difíciles, porque no se conoce ningún algoritmo capaz de resolverlo rápidamente en general.
Por otro lado, cuando se presentan los factores primos de un número, es fácil calcular si son los valores correctos multiplicándolos entre sí.
Por lo tanto, la factorización de primos pertenece a la clase de complejidad NP, que contiene no sólo problemas de cálculo P sino también aquellos que son difíciles de resolver pero que es facil obtener sus respuestas
Sin embargo, el hecho de que aún no se conozca un algoritmo rápido para resolver un problema no significa que no exista.
Así, a principios de los años 70, los informáticos formularon una famosa pregunta: ¿los problemas en P se corresponden con los de NP? O, dicho de otro modo, para cada problema fácil de comprobar, ¿existe un algoritmo que lo resuelva rápidamente?
Cuando Wigderson se incorporó al Technion (el Instituto Tecnológico de Israel) en 1977, el llamado problema P-NP era aún joven. A lo largo de las siguientes décadas, haría muchas contribuciones fundamentales a la misma, determinando qué problemas entran en cada categoría y en qué circunstancias.
La combinación perfecta
A finales de los años 80, Wigderson y su colaborador Ran Raz estudiaron la complejidad del «emparejamiento perfecto» (una cuestión que también aparece en la obra de Lovász): imaginemos que hay 20 máquinas, cada una de las cuales es capaz de realizar algunas -pero no todas- de 20 tareas diferentes.
En el caso de una coincidencia perfecta, se intenta afinar las máquinas para que se cubran todas las tareas y cada máquina realice exactamente una.
Wigderson y Raz estudiaron el problema buscando un algoritmo de correspondencia para resolver la tarea.
Sin embargo, para ello, restringieron las capacidades del ordenador que lo manejaría: imaginaron que el ordenador podría realizar la mayoría de las operaciones lógicas estándar (como «y» y «o»), pero no una operación crucial: la no operación.