Imagine que você está em busca de compreender a própria natureza da computação. Você está nas profundezas do deserto, longe de qualquer caminho, e inescrutável mensagens estão esculpidos nos troncos das árvores ao seu redor - BPP, AC⁰[m], Σ₂P, YACC e centenas de outros. Os glifos estão tentando lhe dizer algo, mas por onde começar? Você não consegue nem mantê-los todos corretos.

Poucos pesquisadores fizeram tanto quanto Russel Impagliazzo para acabar com esse aparente caos. Há 40 anos, Impagliazzo trabalha na vanguarda da teoria da complexidade computacional, o estudo da dificuldade intrínseca de diferentes problemas. A questão aberta mais famosa neste campo, chamada de problema P versus NP, questiona se muitos problemas computacionais aparentemente difíceis são realmente fáceis – com o algoritmo certo. Uma resposta teria implicações de longo alcance para a ciência e para a segurança da criptografia moderna.

Nas décadas de 1980 e 1990, Impagliazzo desempenhou um papel de liderança na unificação do fundamentos teóricos da criptografia. Em 1995, ele articulou o significado destes novos desenvolvimentos num artigo icónico que reformulou possíveis soluções para P versus NP e um punhado de problemas relacionados na linguagem de cinco mundos hipotéticos poderíamos habitar, caprichosamente apelidados de Algorithmica, Heuristica, Pessiland, Minicrypt e Cryptomania. Os cinco mundos de Impagliazzo inspiraram uma geração de investigadores e continuam a orientar a investigação no florescente subcampo da meta-complexidade.

E estes não são os únicos mundos que ele sonhou. Impagliazzo sempre foi um aficionado por jogos de RPG de mesa, como Dungeons and Dragons, e adora inventar novos conjuntos de regras e novas configurações para explorar. O mesmo espírito lúdico anima sua prática de comédia improvisada de 30 anos.

Impagliazzo também fez um trabalho fundamental elucidando o papel fundamental da aleatoriedade na computação. No final da década de 1970, cientistas da computação descobriram que a aleatoriedade às vezes poderia melhorar algoritmos para resolver problemas inerentemente determinísticos – uma descoberta contraintuitiva que deixou os pesquisadores perplexos durante anos. O trabalho de Impagliazzo com o teórico da complexidade Avi Wigderson e outros pesquisadores na década de 1990 mostraram que se certos problemas computacionais são realmente fundamentalmente difíceis, então é sempre possível para converter algoritmos que usam aleatoriedade em algoritmos determinísticos. E, inversamente, provar que a aleatoriedade pode ser eliminada de qualquer algoritmo também provaria que existem problemas verdadeiramente difíceis.

Quanta conversou com Impagliazzo sobre a diferença entre problemas difíceis e quebra-cabeças difíceis, consultando oráculos e as lições matemáticas da comédia improvisada. A entrevista foi condensada e editada para maior clareza.

Quando você começou a se interessar por matemática?

Eu estava interessado em matemática antes mesmo de realmente saber o que era. Na terceira série, minhas notas em matemática começaram a cair porque deveríamos memorizar a tabuada, e eu recusei. Minha mãe disse: “Mas Russell, você adora matemática, por que não está fazendo isso?” E eu disse: “Isso não é matemática, é memorização. A matemática real não envolve memorização.” Tudo o que aprendi naquele momento foi aritmética, então não tenho certeza de onde tirei a noção de que matemática tratava de conceitos abstratos.

E a ciência da computação? Partes do campo são muito abstratas, mas não são o que a maioria das pessoas encontra pela primeira vez.

No ensino médio, eu tinha um curso de programação em BASIC, mas era muito difícil fazer alguma coisa. Os programas tiveram que ser transferidos para fitas de papel, que tiveram que ser executadas neste computador muito antigo que muitas vezes funcionava mal e rasgava o papel ao meio. Então pensei que a ciência da computação era terrivelmente chata.

Eu pretendia estudar lógica. Mas muitos dos conceitos, quando você tentou realmente formalizá-los, envolviam computação e especialmente limites à computação. Perguntas como “Como sabemos que as coisas em matemática são verdadeiras?” e “Como entendemos a dificuldade de fazer matemática?” levou à ciência da computação teórica e, especialmente, à teoria da complexidade.

Alguns de seus trabalhos mais famosos exploram as conexões entre criptografia e teoria da complexidade computacional. Por que esses dois campos estão relacionados?

Ao configurar um sistema criptográfico, você precisa distinguir entre usuários legítimos — as pessoas às quais você deseja conceder acesso — e todas as outras pessoas. Problemas computacionalmente difíceis nos dão uma maneira de distinguir esses grupos com base no que eles sabem. Mas se você quiser que saber a resposta para um problema seja uma forma de distinguir dois grupos de pessoas, você não pode simplesmente usar qualquer problema difícil – você precisa de um quebra-cabeça difícil.

Qual é a diferença entre um problema e um quebra-cabeça?

Em geral, a pessoa que apresenta o problema pode não saber a resposta. Um quebra-cabeça é um problema projetado com uma resposta em mente. Então, por que precisamos de um quebra-cabeça? Porque precisamos ser capazes de determinar se uma pessoa que supostamente resolveu o problema realmente o fez. Na vida cotidiana, usamos quebra-cabeças para nos divertir, mas também os usamos nas salas de aula para testar se as pessoas compreenderam o material. Isto é o que acontece na criptografia: usamos quebra-cabeças para testar o conhecimento de alguém.

A diferença entre os cinco mundos é como eles respondem às perguntas “Existem problemas difíceis?” e “Existem quebra-cabeças difíceis?”

Como essas diferentes respostas funcionam?

No primeiro mundo, Algorithmica, nenhum problema é difícil. Você não precisa saber como alguém projetou seu problema: você sempre pode resolvê-lo. Heurística está dizendo: “Bem, talvez alguns problemas sejam difíceis”. Então chegamos à Pessiland, onde muitos problemas são difíceis, mas a maioria dos quebra-cabeças não. Quase qualquer problema que eu invente e onde conheço a solução, você também será capaz de resolvê-lo. Todos esses mundos são ruins para a criptografia.

No Minicrypt, posso criar quebra-cabeças que sei resolver e que ainda são realmente desafiadores para você. E, finalmente, a Criptomania é um mundo em que duas pessoas podem ficar em um local público onde um bisbilhoteiro pode ouvir e juntas criar um quebra-cabeça que ainda é difícil para o bisbilhoteiro.

O que o motivou a escrever o artigo dos cinco mundos?

Na altura, sabia-se que diferentes respostas à questão P versus NP teriam um grande impacto sobre que tipo de problemas poderíamos resolver e também que tipo de segurança poderíamos esperar, mas as distinções qualitativas entre diferentes formas de facilidade e dureza não eram realmente claras.

Houve um artigo muito esclarecedor apenas alguns anos antes que expôs as distinções usando muitas perguntas inter-relacionadas com cerca de 20 respostas possíveis. Uma razão pela qual quis escrever o artigo dos cinco mundos foi que havíamos feito um enorme progresso nesses poucos anos. Teria sido difícil encontrar nomes para 20 mundos possíveis.

Então, por que enquadrar dessa forma, como mundos diferentes com nomes peculiares?

Eu concordei em escrever este artigo para uma conferência. Eu ficava acordado até tarde da noite tentando descobrir o que iria dizer, e por volta da 1h da manhã o enquadramento dos diferentes mundos parecia uma boa ideia. E então eu li na manhã seguinte e ainda parecia uma ideia boa – era uma forma de mostrar como essas ideias iriam realmente influenciar o mundo sem me prender a detalhes quantitativos. O que me deixa mais feliz com este artigo é que ouço de pessoas que fazem pesquisas em complexidade que este foi o artigo que os interessou pela área quando eram estudantes de graduação.

Os pesquisadores descartaram algum dos cinco mundos possíveis?

Na verdade, estamos adicionando mais — as pessoas começaram a falar sobre Ofustopia como um mundo de ferramentas criptográficas ainda mais fortes. É um pouco deprimente que tenhamos feito tanto progresso no final da década de 1980 e não tenhamos eliminado nenhum mundo desde então. Mas, por outro lado, sabemos muito mais sobre as conexões entre os mundos e temos uma imagem muito mais clara de como seria cada mundo.

Os mundos hipotéticos também desempenham outro papel na teoria da complexidade, em provas que assumem a existência de “oráculos”. Então, antes de mais nada, o que é exatamente um oráculo?

Imagine que alguém construa um dispositivo engenhoso que possa resolver algum problema sem que conheçamos um algoritmo para resolver esse problema. Isso é o que é um oráculo. Se tivéssemos um dispositivo tão milagroso e o colocássemos dentro dos nossos computadores, ele poderia mudar a linha entre o que é computável e o que não é computável.

Os pesquisadores acham que essas caixas mágicas poderiam realmente existir?

Não, eles provavelmente não existem. No início, os resultados do oráculo eram um tanto controversos porque eram muito hipotéticos. Mas uma forma de serem muito esclarecedores é quando o oráculo é usado para modelar uma situação ideal. Digamos que você esteja tentando mostrar que A não implica necessariamente B. Você começa com o cenário onde tem o A mais extremo e mostra que isso ainda não é suficiente para garantir B. Se você puder mostrar isso mesmo que todas as probabilidades sejam a seu favor, você ainda não pode provar algo, isso é uma evidência muito forte de que será difícil provar.

Você também descobriu ligações entre dureza computacional e aleatoriedade. Como funciona essa conexão?

É realmente uma maneira de dizer que se você não entende alguma coisa, então pode parecer aleatório. Suponha que eu diga que estou pensando em um número entre um e mil. Se eu escolher o número aleatoriamente, você terá uma chance em mil de adivinhá-lo. E se eu perguntar – seguindo Monty Python – “Em milhas por hora, qual é a velocidade média de uma andorinha europeia?” você tem quase a mesma chance. Provavelmente percorre mais de um quilômetro por hora e provavelmente não ultrapassa mil quilômetros por hora.

Na verdade, isso não é aleatório - é uma pergunta deterministicamente respondível. Poderíamos apenas medir todas as andorinhas voando, mas é meio difícil de determinar com recursos limitados, como não ter um orçamento para medir a velocidade das andorinhas e não ter um suprimento infinito de andorinhas.

Portanto, a conclusão é que problemas difíceis cujas soluções não conhecemos podem fornecer uma fonte de números “pseudo-aleatórios” que parecem aleatórios.

Falando em Monty Python, sei que você já faz comédia improvisada há muito tempo - como começou?

Comecei como professor assistente em San Diego em 1991. E por volta de 94, pensei: “Realmente não tenho muita vida fora do departamento”. Então peguei o jornal semanal gratuito e dei uma olhada na lista de clubes e atividades. Eliminei tudo, exceto a comédia improvisada - pensei que era pelo menos plausível que eu estivesse bem nisso. Conheci minha esposa naquela turma de iniciantes.

O que ela achou?

Ela diz que eu fui realmente horrível. Quando você é um lógico, é treinado para sempre pensar nas nuances de cada palavra. Você não quer dizer algo incorreto. O improviso é ótimo porque inverte isso: a questão não é dizer algo perfeito, mas inventar algo rapidamente. Foi o oposto do resto da minha vida.

Minha agora esposa fez uma pausa nas aulas e, quando voltou, um ano depois, consegui impressioná-la. Isso foi há 30 anos. Ainda faço a mesma aula com o mesmo instrutor.

Fazer improvisação mudou a maneira como você aborda sua pesquisa?

É uma boa prática não ser hipercrítico em relação a cada pensamento que você tem. Isso é especialmente útil em colaborações. Ao trabalhar com outras pessoas, eu costumava dizer coisas como: “Mas essa ideia não vai funcionar pelo seguinte motivo. Isso não é literalmente verdade.” Na improvisação, você sempre deve aceitar o que seu parceiro diz. E acho que é uma boa atitude, especialmente quando você está pesquisando com alunos: não descarte algo que eles dizem só porque você sabe que está incorreto. Existem muitas boas ideias que não são 100% corretas.

Como o quê?

Quando você está tentando obter intuição para um problema, uma coisa que ajuda é começar com algumas suposições simplificadoras. Essas suposições geralmente não são verdadeiras, mas podem ajudá-lo a elaborar um roteiro. Diga: “Se eu tivesse um elefante, poderia atravessar as montanhas. Claro, não tenho elefante. Mas se eu fizesse, eis como eu faria.” E então você percebe: “Bem, talvez eu não precise de um elefante para esta etapa. Uma mula estaria bem.

E quanto ao seu amor por jogos de RPG – isso influenciou de alguma forma o seu trabalho?

Pode não ter influenciado toda a minha pesquisa, mas certamente influenciou o meu artigo sobre os cinco mundos. Sempre tive um interesse geral por fantasia e ficção científica e por criar diferentes mundos possíveis – como seriam as coisas se tudo fosse diferente?

Por que os jogos de RPG são uma forma tão atraente de explorar mundos hipotéticos?

Pessoas que gostam de ficção especulativa sempre inventaram mundos. Tolkien é mais famoso por isso, e ele tinha uma imaginação tão grande que seu mundo realmente parecia vivido. Para aqueles de nós que não são tão imaginativos, a melhor maneira de conseguir isso é convidar pessoas para o seu ambiente, e um jogo é uma maneira de fazer isso. Agora não é apenas o meu mundo. Pode ter começado como eu imaginava, mas assim como qualquer colaboração, graças às contribuições de todos os outros, evoluiu muito além disso.