Por mais de 40 anos, Avi Wigderson estudou problemas. Mas, como teórico da complexidade computacional, ele não se preocupa necessariamente com as respostas para esses problemas. Muitas vezes, ele só quer saber se eles podem ser resolvidos ou não e como saber. “A situação é ridícula”, disse Widerson, cientista da computação do Instituto de Estudos Avançados de Princeton, Nova Jersey. Não importa o quão difícil uma pergunta pareça, uma maneira eficiente de respondê-la pode estar escondida, fora de alcance. “Até onde sabemos, para cada problema que enfrentamos e tentamos resolver, não podemos descartar que exista um algoritmo que possa resolvê-lo. Este é o problema mais interessante para mim.”

Hoje Wigderson foi eleito o vencedor do Prêmio AM Turing, amplamente considerado uma das maiores homenagens da ciência da computação, por suas contribuições fundamentais à teoria da computação. O trabalho de Wigderson tocou quase todas as áreas da área. Seus colegas, colaboradores e pupilos dizem que ele sempre encontra pontes inesperadas entre áreas díspares. E o seu trabalho sobre aleatoriedade e computação, iniciado na década de 1990, revelou conexões profundas entre a matemática e a ciência da computação que estão subjacentes às investigações atuais.

Madhu Sudão, um cientista da computação da Universidade de Harvard que ganhou o Prêmio Rolf Nevanlinna em 2002 (agora chamado de Prêmio Abacus), disse que a influência de Wigderson na área é impossível de ignorar. “É muito difícil trabalhar em qualquer área da ciência da computação sem realmente cruzar com o trabalho de Avi”, disse Sudan. “E em todos os lugares você encontra insights muito profundos.” No final da década de 1980, por exemplo, Sudan trabalhou com Wigderson num artigo que investigava ligações entre certas funções matemáticas e polinómios. Esse trabalho lançou toda a carreira do Sudão. “Isso é típico de Avi”, disse Sudan. “Ele entra em algum espaço, faz as perguntas certas e depois segue em frente.”

Wigderson cresceu em Haifa, Israel, como um dos três filhos de uma enfermeira e de um engenheiro elétrico, ambos sobreviventes do Holocausto. Seu pai adorava quebra-cabeças e se interessava intensamente pelas ideias fundamentais da matemática, que compartilhava com os filhos. “Ele é o cara por quem fui infectado por esse vírus”, disse Wigderson. Quando começou a faculdade, na década de 1970, na Universidade de Haifa, ele queria se formar em matemática, mas seus pais o orientaram para ciência da computação. “Eles pensaram que talvez fosse uma boa ideia eu ter um emprego quando terminasse”, disse ele.

Ele encontrou um campo rico em questões profundas e sem resposta que, no fundo, eram matemáticas. Um dos seus primeiros esforços inovadores centrou-se numa aparente contradição: se era possível convencer alguém de que uma afirmação matemática tinha sido provada sem mostrar como.

“A pessoa que vê a prova não aprende nada sobre a prova em si”, disse Correu Raz, cientista da computação da Universidade de Princeton. Em 1985, Shafi Goldwasser, Silvio Micali e Charles Rackoff introduziram este conceito de provas interativas de conhecimento zero, demonstrando seu uso para algumas declarações. Wigderson, juntamente com Micali e Oded Goldreich, mais tarde expôs essa ideia, expondo as condições que mostram que se uma afirmação pode ser provada, ela também tem uma prova de conhecimento zero.

“Este é um resultado importante em criptografia; é extremamente central”, disse Raz. Usando uma prova de conhecimento zero, alguém pode provar que criptografou ou assinou corretamente uma mensagem usando sua chave secreta, sem revelar qualquer informação sobre ela. “Avi tem alguns resultados extremamente importantes em criptografia, e este pode ser o mais importante deles.”

Mas talvez o resultado mais fundamental de Wigderson esteja em outra área: vincular a dureza computacional à aleatoriedade. No final da década de 1970, os cientistas da computação perceberam que, para muitos problemas difíceis, os algoritmos que empregavam aleatoriedade, também chamados de algoritmos probabilísticos, poderiam superar amplamente as alternativas determinísticas. Em um Prova de 1977, por exemplo, Robert Solovay e Volker Strassen introduziram um algoritmo aleatório que poderia determinar se um número é primo mais rápido do que os melhores algoritmos determinísticos da época.

Para alguns problemas, algoritmos probabilísticos podem apontar para problemas determinísticos. No início da década de 1980, Wigderson trabalhou com Richard Karp, da Universidade da Califórnia, Berkeley, para conectar a ideia de aleatoriedade a problemas considerados computacionalmente difíceis, o que significa que nenhum algoritmo determinístico conhecido pode resolvê-los em um período de tempo razoável. “Não sabemos como provar que eles são difíceis”, disse Wigderson. No entanto, ele e Karp encontraram um algoritmo randomizado para um determinado problema difícil que mais tarde foram capazes de desrandomizar, descobrindo efetivamente um algoritmo determinístico para ele. Na mesma época, outros pesquisadores mostraram como as suposições de dureza computacional em problemas de criptografia poderiam permitir a desrandomização em geral.

A eficácia irracional da aleatoriedade levou-o a pensar sobre a natureza da própria aleatoriedade. Ele, como outros pesquisadores da época, questionou até que ponto isso era necessário para a resolução eficiente de problemas e em que condições poderia ser totalmente eliminado. “Inicialmente, não estava claro se isso era apenas nossa própria estupidez, que não podemos eliminar a aleatoriedade”, disse ele. “Mas a questão maior era se a aleatoriedade sempre pode ser eliminada de forma eficiente ou não.” Ele percebeu que a necessidade de aleatoriedade estava intimamente ligada à dificuldade computacional do problema.

Para uma papel 1994, ele e o cientista da computação Noam Nisan esclareceram essa conexão. Eles provaram que, se existir algum problema natural difícil, como a maioria dos cientistas da computação suspeita, então todo algoritmo aleatório eficiente pode ser substituído por um determinístico eficiente. “Você sempre pode eliminar a aleatoriedade”, disse Wigderson.

É importante ressaltar que eles descobriram que algoritmos determinísticos podem usar sequências “pseudo-aleatórias” – sequências de dados que parecem aleatórias, mas não são. Eles também mostraram como qualquer problema difícil pode ser usado para construir um gerador pseudoaleatório. Alimentar os bits pseudoaleatórios (em vez dos aleatórios) em um algoritmo probabilístico resultará em um algoritmo determinístico eficiente para o mesmo problema.

Sudão disse que o artigo ajudou os cientistas da computação a reconhecer graus de aleatoriedade que poderiam ajudar a revelar as complexidades de problemas difíceis e como resolvê-los. “Não se trata apenas de aleatoriedade, mas de percepções de aleatoriedade”, disse ele. “Essa é a chave.”

Sudão salienta que a aleatoriedade parece aparecer em todo o lado, mas é, na verdade, extremamente difícil de encontrar. “As pessoas dizem que os dígitos de pi parecem aleatórios, ou que a sequência de números primos parece aleatória”, disse ele. “Eles estão completamente determinados, mas parecem aleatórios para nós.” A percepção da aleatoriedade, disse ele, está no cerne da ciência da computação hoje. “E isso é algo que Avi promoveu amplamente.”

A aleatoriedade tornou-se um recurso poderoso na teoria da complexidade, mas é evasivo. Os lançamentos de moedas e de dados, ressalta Wigderson, não são verdadeiramente aleatórios: se você tiver informações suficientes sobre o sistema físico, o resultado será totalmente previsível. A aleatoriedade perfeita, disse ele, é ilusória e difícil de verificar.

Mas para Wigerson, os exemplos de computação estão por toda parte – não apenas em smartphones, laptops e algoritmos de criptografia, mas também em sistemas biológicos e físicos. Nas últimas décadas, as descobertas da teoria da computação produziram insights sobre uma série de problemas inesperados, desde enxames de pássaros e resultados eleitorais até reações bioquímicas no corpo. “Basicamente, qualquer processo natural é uma evolução que você pode ver como computação, então você pode estudá-la como tal. Quase tudo computa.”