Durante más de 40 años, Avi Wigderson ha estudiado problemas. Pero como teórico de la complejidad computacional, no necesariamente le importan las respuestas a estos problemas. A menudo sólo quiere saber si se pueden solucionar o no, y cómo saberlo. "La situación es ridícula", dijo Widderson, científico informático del Instituto de Estudios Avanzados de Princeton, Nueva Jersey. No importa lo difícil que parezca una pregunta, una forma eficaz de responderla podría ser esconderse fuera de su alcance. “Hasta donde sabemos, para cada problema que enfrentamos y tratamos de resolver, no podemos descartar que tenga un algoritmo que pueda resolverlo. Éste es el problema más interesante para mí”.

Hoy Wigderson fue nombrado ganador del Premio AM Turing, ampliamente considerado uno de los máximos honores en ciencias de la computación, por sus contribuciones fundamentales a la teoría de la computación. El trabajo de Wigderson ha tocado casi todas las áreas del campo. Sus colegas, colaboradores y aprendices dicen que constantemente encuentra puentes inesperados entre áreas dispares. Y su trabajo sobre aleatoriedad y computación, que comenzó en la década de 1990, reveló profundas conexiones entre las matemáticas y la informática que subyacen a las investigaciones actuales.

Madhu Sudán, un científico informático de la Universidad de Harvard que ganó el Premio Rolf Nevanlinna en 2002 (ahora llamado Premio Abacus), dijo que es imposible pasar por alto la influencia de Wigderson en este campo. "Es muy difícil trabajar en cualquier ámbito de la informática sin cruzarse con el trabajo de Avi", dijo Sudan. “Y en todas partes se encuentran ideas muy profundas”. A finales de los años 1980, por ejemplo, Sudán trabajó con Wigderson en un artículo que investigaba las conexiones entre ciertas funciones matemáticas y polinomios. Ese trabajo lanzó toda la carrera de Sudán. "Esto es típico de Avi", dijo Sudan. "Entra en un espacio, hace las preguntas correctas y luego sigue adelante".

Wigderson creció en Haifa, Israel, como uno de los tres hijos de una enfermera y un ingeniero eléctrico, ambos sobrevivientes del Holocausto. A su padre le encantaban los rompecabezas y estaba intensamente interesado en las ideas fundamentales de las matemáticas, que compartía con sus hijos. "Él es el tipo que me infectó con este virus", dijo Wigderson. Cuando comenzó la universidad en la década de 1970, en el Technion de Haifa, quería especializarse en matemáticas, pero sus padres lo orientaron hacia ciencias de la computación. “Pensaron que tal vez era una buena idea que tuviera un trabajo cuando terminara”, dijo.

Encontró un campo rico en preguntas profundas y sin respuesta que eran matemáticas en el fondo. Uno de sus primeros esfuerzos innovadores se centró en una aparente contradicción: si era posible convencer a alguien de que un enunciado matemático había sido demostrado sin mostrar cómo.

"La persona que ve la prueba no aprende nada sobre la prueba en sí", dijo Corrió Raz, científico informático de la Universidad de Princeton. En 1985, Shafi Goldwasser, Silvio Micali y Charles Rackoff introdujeron este concepto de pruebas interactivas de conocimiento cero, demostrando su uso para algunas declaraciones. Wigderson, junto con Micali y Oded Goldreich, expusieron más tarde esa idea y expusieron las condiciones que demuestran que si una afirmación puede probarse, también tiene una prueba de conocimiento cero.

“Este es un resultado clave en criptografía; es extremadamente central”, dijo Raz. Utilizando una prueba de conocimiento cero, alguien puede demostrar que cifró o firmó correctamente un mensaje usando su clave secreta, sin revelar ninguna información al respecto. "Avi tiene algunos resultados extremadamente importantes en criptografía, y este puede ser el más importante de ellos".

Pero quizás el resultado más fundamental de Wigderson se encuentre en otra área: vincular la dureza computacional con aleatoriedad. A finales de la década de 1970, los científicos informáticos se habían dado cuenta de que, para muchos problemas difíciles, los algoritmos que empleaban aleatoriedad, también llamados algoritmos probabilísticos, podían superar ampliamente a sus alternativas deterministas. en un 1977 pruebasPor ejemplo, Robert Solovay y Volker Strassen introdujeron un algoritmo aleatorio que podía determinar si un número es primo más rápido que los mejores algoritmos deterministas de esa época.

Para algunos problemas, los algoritmos probabilísticos pueden apuntar a otros deterministas. A principios de la década de 1980, Wigderson trabajó con Richard Karp de la Universidad de California, Berkeley, para conectar la idea de aleatoriedad con problemas considerados computacionalmente difíciles, lo que significa que ningún algoritmo determinista conocido puede resolverlos en un período de tiempo razonable. "No sabemos cómo demostrar que son duros", dijo Wigderson. Sin embargo, él y Karp encontraron un algoritmo aleatorio para cierto problema difícil que luego pudieron desaleatorizar, descubriendo efectivamente un algoritmo determinista para él. Casi al mismo tiempo, otros investigadores demostraron cómo los supuestos de dureza computacional en problemas de criptografía podrían permitir la desaleatorización en general.

La irrazonable eficacia de la aleatoriedad lo llevó a pensar en la naturaleza de la aleatoriedad misma. Él, al igual que otros investigadores de la época, se preguntó hasta qué punto era necesario para una resolución eficaz de problemas y en qué condiciones podría eliminarse por completo. "Al principio no estaba claro si se trataba sólo de nuestra propia estupidez, de que no podemos eliminar la aleatoriedad", dijo. "Pero la pregunta más importante era si la aleatoriedad siempre se puede eliminar de manera eficiente o no". Se dio cuenta de que la necesidad de aleatoriedad estaba íntimamente ligada a la dificultad computacional del problema.

Para una papel 1994, él y el informático Noam Nisan iluminaron esa conexión. Demostraron que si existen problemas naturales difíciles, como sospechan la mayoría de los informáticos, entonces todo algoritmo aleatorio eficiente puede ser reemplazado por uno determinista eficiente. "Siempre se puede eliminar la aleatoriedad", dijo Wigderson.

Es importante destacar que descubrieron que los algoritmos deterministas pueden utilizar secuencias "pseudoaleatorias": cadenas de datos que parecen aleatorias pero no lo son. También mostraron cómo se pueden utilizar problemas difíciles para construir un generador pseudoaleatorio. Introducir los bits pseudoaleatorios (en lugar de los aleatorios) en un algoritmo probabilístico dará como resultado uno determinista eficiente para el mismo problema.

Sudan dijo que el artículo ayudó a los científicos informáticos a reconocer grados de aleatoriedad que podrían ayudar a revelar las complejidades de problemas difíciles y cómo resolverlos. "No se trata sólo de aleatoriedad sino de percepciones de aleatoriedad", dijo. "Esa es la clave".

Sudán señala que la aleatoriedad parece aparecer en todas partes pero, en realidad, es extremadamente difícil de encontrar. "La gente te dice que los dígitos de pi parecen aleatorios, o que la secuencia de números primos parece aleatoria", dijo. "Están completamente decididos, pero a nosotros nos parecen aleatorios". La percepción de aleatoriedad, afirmó, se encuentra en el corazón de la informática actual. "Y eso es algo que Avi ha promovido enormemente".

La aleatoriedad se ha convertido en un recurso poderoso en la teoría de la complejidad, pero es difícil de alcanzar. Los lanzamientos de monedas y dados, señala Wigderson, no son verdaderamente aleatorios: si se tiene suficiente información sobre el sistema físico, entonces el resultado es completamente predecible. La aleatoriedad perfecta, afirmó, es esquiva y difícil de verificar.

Pero para Wigerson, los ejemplos de informática están en todas partes, no sólo en los teléfonos inteligentes, las computadoras portátiles y los algoritmos de cifrado, sino también en los sistemas biológicos y físicos. En las últimas décadas, los hallazgos de la teoría de la computación han aportado conocimientos sobre una variedad de problemas inesperados, desde enjambres de pájaros y resultados electorales hasta reacciones bioquímicas en el cuerpo. “Básicamente, cualquier proceso natural es una evolución que se puede ver como computación, por lo que se puede estudiar como tal. Casi todo se computa”.