Problemas computacionales y robots. Concepto del pensamiento

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.

Robots cuidando robots

“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.