Avi Wigderson foi nomeado nesta quarta-feira, 10, o vencedor do Prêmio Turing, considerado o “Oscar das ciências da computação”, por suas contribuições fundamentais à teoria da computação. O trabalho de Wigderson atingiu quase todas as áreas do campo. Seus colegas, colaboradores e pupilos dizem que ele sempre encontra pontes inesperadas entre áreas diferentes. E 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 fundamentam as investigações atuais.
Por mais de 40 anos, Wigderson estudou problemas, mas, como teórico da complexidade computacional, ele não se preocupa necessariamente com as respostas a esses problemas. Muitas vezes, ele só quer saber se eles são solucionáveis ou não, e como saber isso. “A situação é ridícula”, diz Wigderson, cientista da computação do Institute for Advanced Study em Princeton, Nova Jersey, EUA. Por mais difícil que uma pergunta pareça, uma maneira eficiente de respondê-la pode estar escondida fora do alcance. “Até onde sabemos, para cada problema que enfrentamos e tentamos resolver, não podemos descartar a possibilidade de haver um algoritmo que possa resolvê-lo. Esse é o problema mais interessante para mim.”
Leia também
Madhu Sudan, cientista da computação da Universidade Harvard que ganhou o Prêmio Rolf Nevanlinna de 2002 (agora chamado de Prêmio Abacus), diz que é impossível não notar a influência de Wigderson na área. “É muito difícil trabalhar em qualquer área da ciência da computação sem ter contato com o trabalho de Avi”, disse Sudan. “E em todos os lugares, você encontra percepções muito profundas.” No final da década de 1980, por exemplo, Sudan trabalhou com Wigderson em um artigo que investigava as conexões entre determinadas funções matemáticas e polinômios. Esse trabalho deu início a toda a carreira de Sudan. “Isso é típico de Avi”, disse Sudan. “Ele entra em um espaço, faz as perguntas certas e depois segue em frente.”
Wigderson foi criado 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 tinha grande interesse em ideias fundamentais da matemática, que compartilhava com os filhos. “Ele foi a pessoa que me infectou com esse vírus”, diz 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 a ciência da computação. “Eles acharam 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 eram matemáticas em sua essência. Um de seus primeiros esforços inovadores concentrou-se em uma aparente contradição: se era possível convencer alguém de que uma afirmação matemática havia sido provada sem mostrar como.
“A pessoa que vê a prova não aprende nada sobre a prova em si”, disse Ran Raz, cientista da computação da Universidade de Princeton. Em 1985, Shafi Goldwasser, Silvio Micali e Charles Rackoff introduziram esse conceito de provas interativas de conhecimento zero, demonstrando seu uso para algumas afirmações. Mais tarde, Wigderson, juntamente com Micali e Oded Goldreich, expôs essa ideia, estabelecendo as condições que mostram que, se uma declaração pode ser provada, ela também tem uma prova de conhecimento zero.
“Esse é um resultado importante na criptografia; é extremamente central”, diz Raz. Usando uma prova de conhecimento zero, alguém pode provar que criptografou ou assinou corretamente uma mensagem usando sua chave secreta, sem revelar nenhuma informação sobre ela. “Avi tem alguns resultados extremamente importantes em criptografia, e esse pode ser o mais importante deles.”
Mestre da aleatoriedade
Mas talvez o resultado mais fundamental de Wigderson esteja em outra área: vincular a dificuldade 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 suas alternativas determinísticas. Em uma prova de 1977, por exemplo, Robert Solovay e Volker Strassen apresentaram um algoritmo aleatório capaz de determinar se um número é primo mais rapidamente do que os melhores algoritmos determinísticos da época.
Para alguns problemas, os algoritmos probabilísticos podem apontar para os determinísticos. No início da década de 1980, Wigderson trabalhou com Richard Karp, da Universidade da Califórnia, em 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 descobriram um algoritmo aleatório para um determinado problema difícil que, mais tarde, puderam desarmazenar, 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 desaleatorização em geral.
A eficácia irracional da aleatoriedade o levou a pensar sobre a natureza da própria aleatoriedade. Ele, assim como outros pesquisadores na época, questionou o quanto ela era necessária para a solução eficiente de problemas e sob quais condições ela poderia ser eliminada completamente. “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.
Em um artigo de 1994, ele e o cientista da computação Noam Nisan esclareceram essa conexão. Eles provaram que, se existirem problemas naturais difíceis, como a maioria dos cientistas da computação suspeita, todo algoritmo aleatório eficiente pode ser substituído por um determinístico eficiente. “Sempre é possível eliminar a aleatoriedade”, disse Wigderson.
É importante ressaltar que eles descobriram que os 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 criar um gerador pseudo-aleatório. A alimentação dos bits pseudoaleatórios (em vez dos aleatórios) em um algoritmo probabilístico resultará em um algoritmo determinístico eficiente para o mesmo problema.
Sudan 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.”
Sudan ressalta que a aleatoriedade parece aparecer em todos os lugares, mas, na verdade, é extremamente difícil de ser encontrada. “As pessoas dizem que os dígitos de pi parecem aleatórios, ou que a sequência de números primos parece aleatória”, diz ele. “Eles são completamente determinados, mas parecem aleatórios para nós.” A percepção da aleatoriedade, segundo ele, está no centro da ciência da computação atualmente. “E isso é algo que a Avi promoveu enormemente.”
A aleatoriedade se tornou um recurso poderoso na teoria da complexidade, mas é elusiva. O lançamento de moedas e de dados, ressalta Wigderson, não é realmente aleatório: Se você tiver informações suficientes sobre o sistema físico, o resultado será totalmente previsível. A aleatoriedade perfeita, segundo ele, é ilusória e difícil de verificar.
Mas para Wigerson, exemplos de computação estão em 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 percepções sobre uma série de problemas inesperados, desde enxames de pássaros e resultados de eleições até reações bioquímicas no corpo. “Basicamente, qualquer processo natural é uma evolução que pode ser vista como computação e, portanto, pode ser estudada como tal. Quase tudo é computado.”
História original republicada com permissão da Quanta Magazine, uma publicação editorialmente independente apoiada pela Simons Foundation. Leia o conteúdo original em Avi Wigderson, Complexity Theory Pioneer, Wins Turing Award
Este conteúdo foi traduzido com o auxílio de ferramentas de Inteligência Artificial e revisado por nossa equipe editorial. Saiba mais em nossa Política de IA.