Para algoritmos, a memória é um recurso muito mais poderoso do que o tempo

A versão original desta história apareceu na Quanta Magazine .

Numa tarde de julho de 2024, Ryan Williams decidiu provar que estava errado. Dois meses haviam se passado desde que ele fizera uma descoberta surpreendente sobre a relação entre tempo e memória na computação. Era um esboço de uma prova matemática de que a memória era mais poderosa do que os cientistas da computação acreditavam: uma pequena quantidade seria tão útil quanto muito tempo em todas as computações imagináveis. Isso parecia tão improvável que ele presumiu que algo estava errado e prontamente deixou a prova de lado para se concentrar em ideias menos malucas. Agora, ele finalmente havia encontrado tempo para encontrar o erro.

Não foi isso que aconteceu. Depois de horas analisando seu argumento, Williams não conseguiu encontrar uma única falha.

"Eu simplesmente pensei que estava perdendo a razão", disse Williams, cientista teórico da computação do Instituto de Tecnologia de Massachusetts. Pela primeira vez, ele começou a cogitar a possibilidade de que talvez, apenas talvez, a memória fosse realmente tão poderosa quanto seu trabalho sugeria.

Ao longo dos meses seguintes, ele aprimorou os detalhes, examinou cada etapa e solicitou feedback de vários outros pesquisadores. Em fevereiro, ele finalmente publicou sua prova online , recebendo ampla aclamação.

"É incrível. É lindo", disse Avi Wigderson , cientista teórico da computação do Instituto de Estudos Avançados de Princeton, Nova Jersey. Assim que soube da notícia, Wigderson enviou a Williams um e-mail de parabéns. O assunto era: "Você me surpreendeu".

Tempo e memória (também chamados de espaço) são os dois recursos mais fundamentais na computação: todo algoritmo leva algum tempo para ser executado e requer algum espaço para armazenar dados enquanto está em execução. Até agora, os únicos algoritmos conhecidos para realizar determinadas tarefas exigiam uma quantidade de espaço aproximadamente proporcional ao seu tempo de execução, e os pesquisadores há muito presumiam que não havia como fazer melhor. A prova de Williams estabeleceu um procedimento matemático para transformar qualquer algoritmo — não importa o que ele faça — em uma forma que ocupe muito menos espaço.

Além disso, esse resultado — uma afirmação sobre o que se pode computar dado um certo espaço — também implica um segundo resultado, sobre o que não se pode computar em um certo período de tempo. Esse segundo resultado não é surpreendente em si: os pesquisadores esperavam que fosse verdade, mas não tinham ideia de como prová-lo. A solução de Williams, baseada em seu primeiro resultado abrangente, parece quase caricaturalmente excessiva, semelhante a provar a culpa de um suposto assassino estabelecendo um álibi infalível para todos os outros no planeta. Também pode oferecer uma nova maneira de atacar um dos problemas em aberto mais antigos da ciência da computação.

"É um resultado impressionante e um avanço enorme", disse Paul Beame , cientista da computação da Universidade de Washington. "É um pouco menos surpreendente que seja Ryan quem esteja fazendo isso."

Williams, de 46 anos, tem um rosto franco e expressivo e alguns fios grisalhos no cabelo. Seu escritório, com vista para as torres coloridas do Stata Center do MIT, é mais um exemplo do uso criativo do espaço. Um par de tapetes de ioga transformou o parapeito de uma janela em um recanto improvisado para leitura, e a mesa está escondida em um canto de formato peculiar, abrindo espaço para um sofá de frente para um grande quadro branco repleto de rabiscos matemáticos.

O MIT fica bem longe da casa de infância de Williams, na zona rural do Alabama, onde não faltava espaço. Ele cresceu em uma fazenda de 20 hectares e viu um computador pela primeira vez aos 7 anos, quando sua mãe o levou de carro pelo condado para uma aula especial de enriquecimento acadêmico. Ele se lembra de ter ficado fascinado por um programa simples para gerar um show digital de fogos de artifício.

"Era como pegar uma cor aleatória e enviá-la em uma direção aleatória a partir do centro do monitor", disse Williams. "Não dava para prever que imagem seria obtida." O mundo dos computadores parecia um playground selvagem e maravilhoso, cheio de possibilidades infinitas. O jovem Williams ficou fascinado.

"Eu estava escrevendo programas para mim mesmo, no papel, para serem executados em um computador do futuro", disse ele. "Meus pais não sabiam bem o que fazer comigo."

À medida que crescia, Williams passou de computadores imaginários para computadores reais. Nos últimos dois anos do ensino médio, transferiu-se para a Escola de Matemática e Ciências do Alabama, um prestigiado internato público, onde teve seu primeiro contato com o lado teórico da ciência da computação.

“Percebi que havia um mundo mais amplo de coisas lá fora e que havia uma maneira de pensar matematicamente sobre computadores”, disse ele. “Era isso que eu queria fazer.”

Williams sentiu-se especialmente atraído por um ramo da ciência da computação teórica chamado teoria da complexidade computacional. Ela lida com os recursos (como tempo e espaço) necessários para resolver problemas computacionais, como ordenação de listas ou fatoração de números. A maioria dos problemas pode ser resolvida por diversos algoritmos diferentes, cada um com suas próprias demandas de tempo e espaço. Os teóricos da complexidade classificam os problemas em categorias, chamadas classes de complexidade, com base nas demandas de recursos dos melhores algoritmos para resolvê-los — ou seja, os algoritmos que executam mais rápido ou usam a menor quantidade de espaço.

Mas como tornar o estudo de recursos computacionais matematicamente rigoroso? Você não chegará longe se tentar analisar tempo e espaço comparando minutos a megabytes. Para progredir, você precisa começar com as definições corretas.

Essas definições surgiram do trabalho de Juris Hartmanis, um cientista da computação pioneiro com experiência em lidar com recursos limitados. Ele nasceu em 1928 em uma família proeminente da Letônia, mas sua infância foi interrompida pela eclosão da Segunda Guerra Mundial. As forças soviéticas de ocupação prenderam e executaram seu pai e, após a guerra, Hartmanis concluiu o ensino médio em um campo de refugiados. Ele ingressou na universidade, onde se destacou, mesmo sem poder comprar livros didáticos.

"Eu compensava isso tomando notas muito detalhadas nas aulas", lembrou ele em uma entrevista de 2009. "Há uma certa vantagem em [ter] que improvisar e superar dificuldades." Hartmanis imigrou para os Estados Unidos em 1949 e trabalhou em uma série de empregos temporários — construindo máquinas agrícolas, fabricando aço e até servindo como mordomo — enquanto estudava matemática na Universidade de Kansas City. Ele seguiu para uma carreira espetacularmente bem-sucedida no jovem campo da ciência da computação teórica.

Em 1960, enquanto trabalhava no laboratório de pesquisa da General Electric em Schenectady, Nova York, Hartmanis conheceu Richard Stearns, um estudante de pós-graduação em estágio de verão. Em dois artigos inovadores , eles estabeleceram definições matemáticas precisas para tempo e espaço. Essas definições deram aos pesquisadores a linguagem necessária para comparar os dois recursos e classificar os problemas em classes de complexidade.

Uma das classes mais importantes é conhecida pelo humilde nome de "P". Em termos gerais, ela abrange todos os problemas que podem ser resolvidos em um período de tempo razoável. Uma classe de complexidade análoga para o espaço é chamada de "PSPACE".

A relação entre essas duas classes é uma das questões centrais da teoria da complexidade. Todo problema em P também está em PSPACE, porque algoritmos rápidos simplesmente não têm tempo suficiente para preencher muito espaço na memória de um computador. Se a afirmação inversa também fosse verdadeira, as duas classes seriam equivalentes: espaço e tempo teriam poder computacional comparável. Mas os teóricos da complexidade suspeitam que PSPACE seja uma classe muito maior, contendo muitos problemas que não estão em P. Em outras palavras, eles acreditam que o espaço é um recurso computacional muito mais poderoso do que o tempo. Essa crença decorre do fato de que os algoritmos podem usar o mesmo pequeno pedaço de memória repetidamente, enquanto o tempo não é tão indulgente — uma vez que ele passa, você não pode recuperá-lo.

"A intuição é tão simples", disse Williams. "Você pode reutilizar o espaço, mas não pode reutilizar o tempo."

Mas a intuição não é suficiente para os teóricos da complexidade: eles querem provas rigorosas. Para provar que PSPACE é maior que P, os pesquisadores teriam que mostrar que, para alguns problemas em PSPACE, algoritmos rápidos são categoricamente impossíveis. Por onde eles começariam?

Acontece que eles começaram na Universidade Cornell, para onde Hartmanis se mudou em 1965 para chefiar o recém-criado departamento de ciência da computação. Sob sua liderança, o departamento rapidamente se tornou um centro de pesquisa em teoria da complexidade e, no início da década de 1970, dois pesquisadores, John Hopcroft e Wolfgang Paul, se propuseram a estabelecer uma ligação precisa entre tempo e espaço.

Hopcroft e Paul sabiam que, para resolver o problema P versus PSPACE, teriam que provar que não é possível realizar certos cálculos em um tempo limitado. Mas é difícil provar uma negativa. Em vez disso, decidiram inverter o problema e explorar o que é possível fazer com espaço limitado. Eles esperavam provar que algoritmos com um determinado orçamento de espaço podem resolver todos os mesmos problemas que algoritmos com um orçamento de tempo ligeiramente maior. Isso indicaria que o espaço é pelo menos um pouco mais poderoso que o tempo — um pequeno, mas necessário passo para mostrar que PSPACE é maior que P.

Com esse objetivo em mente, eles recorreram a um método que os teóricos da complexidade chamam de simulação, que envolve transformar algoritmos existentes em novos que resolvem os mesmos problemas, mas com diferentes quantidades de espaço e tempo. Para entender a ideia básica, imagine que você recebe um algoritmo rápido para organizar sua estante em ordem alfabética, mas que exige que você organize seus livros em dezenas de pequenas pilhas. Você pode preferir uma abordagem que ocupe menos espaço em seu apartamento, mesmo que demore mais. Uma simulação é um procedimento matemático que você pode usar para obter um algoritmo mais adequado: alimente-o com o original e ele fornecerá um novo algoritmo que economiza espaço em detrimento do tempo.

Os projetistas de algoritmos estudam há muito tempo essas compensações espaço-temporais para tarefas específicas, como a ordenação. Mas, para estabelecer uma relação geral entre tempo e espaço, Hopcroft e Paul precisavam de algo mais abrangente: um procedimento de simulação que economizasse espaço e funcionasse para todos os algoritmos, independentemente do problema que resolvessem. Eles esperavam que essa generalidade tivesse um custo. Uma simulação universal não consegue explorar os detalhes de nenhum problema específico, portanto, provavelmente não economizará tanto espaço quanto uma simulação especializada. Mas quando Hopcroft e Paul começaram seu trabalho, não havia métodos universais conhecidos para economizar espaço. Mesmo uma pequena economia já seria um progresso.

O grande avanço veio em 1975, depois que Hopcroft e Paul se uniram a uma jovem pesquisadora chamada Leslie Valiant . O trio desenvolveu um procedimento de simulação universal que sempre economiza um pouco de espaço. Independentemente do algoritmo que você usar, obterá um equivalente com um orçamento de espaço ligeiramente menor do que o orçamento de tempo do algoritmo original.

"Tudo o que você pode fazer em tanto tempo, também pode fazer em um espaço um pouco menor", disse Valiant. Foi o primeiro grande passo na busca para conectar espaço e tempo.

Mas então o progresso estagnou, e os teóricos da complexidade começaram a suspeitar que haviam encontrado uma barreira fundamental. O problema era precisamente o caráter universal da simulação de Hopcroft, Paul e Valiant. Embora muitos problemas possam ser resolvidos com muito menos espaço do que tempo, alguns intuitivamente pareciam precisar de quase tanto espaço quanto tempo. Se assim fosse, simulações universais mais eficientes em termos de espaço seriam impossíveis. Paul e dois outros pesquisadores logo provaram que elas são de fato impossíveis , desde que se faça uma suposição aparentemente óbvia: diferentes blocos de dados não podem ocupar o mesmo espaço na memória ao mesmo tempo.

“Todos achavam que não era possível fazer melhor”, disse Wigderson.

O resultado de Paul sugeriu que resolver o problema P versus PSPACE exigiria abandonar completamente a simulação em favor de uma abordagem diferente, mas ninguém tinha boas ideias. Foi nesse ponto que o problema permaneceu por 50 anos — até que Williams finalmente resolveu o impasse.

Primeiro, ele tinha que terminar a faculdade.

Em 1996, chegou a hora de Williams se candidatar a uma faculdade. Ele sabia que estudar teoria da complexidade o levaria para longe de casa, mas seus pais deixaram claro que a Costa Oeste e o Canadá estavam fora de cogitação. Entre as opções restantes, Cornell se destacou por seu lugar de destaque na história de sua disciplina favorita.

"Esse cara, Hartmanis, definiu as classes de complexidade de tempo e espaço", ele se lembra de ter pensado. "Isso foi importante para mim."

Williams foi admitido em Cornell com generosa bolsa de estudos e chegou no outono de 1997, planejando fazer o que fosse preciso para se tornar um teórico da complexidade. Sua determinação impressionou seus colegas.

“Ele era simplesmente super-super interessado na teoria da complexidade”, disse Scott Aaronson , um cientista da computação da Universidade do Texas, em Austin, que trabalhou com Williams em Cornell.

Mas, no segundo ano, Williams estava com dificuldades para acompanhar os cursos que priorizavam o rigor matemático em detrimento da intuição. Depois de tirar uma nota mediana em uma disciplina sobre teoria da computação, o professor sugeriu que ele considerasse outras carreiras. Mas Williams não desistiu do seu sonho. Ele se esforçou e matriculou-se em um curso de teoria para a pós-graduação, na esperança de que uma nota excepcional na disciplina mais difícil impressionasse em suas inscrições para a pós-graduação. O professor que ministrava a disciplina era Hartmanis, já então um veterano na área.

Williams começou a frequentar o horário de expediente de Hartmanis toda semana, onde era quase sempre o único aluno a comparecer. Sua tenacidade valeu a pena: ele tirou nota A na disciplina, e Hartmanis concordou em orientá-lo em um projeto de pesquisa independente no semestre seguinte. Seus encontros semanais continuaram durante todo o período de Williams na faculdade. Hartmanis o incentivou a cultivar uma abordagem individual à pesquisa da complexidade e gentilmente o afastou de becos sem saída.

"Fui profundamente influenciado por ele naquela época", disse Williams. "Acho que ainda sou."

Mas, apesar de ter conquistado uma cobiçada bolsa de pesquisa de pós-graduação da National Science Foundation, Williams foi rejeitado por todos os programas de doutorado aos quais se candidatou. Ao saber da notícia, Hartmanis telefonou para um colega e, em seguida, parabenizou Williams por ter sido aceito em um programa de mestrado de um ano na Universidade Cornell. Um ano depois, Williams se candidatou novamente a vários programas de doutorado e, com essa experiência extra em pesquisa, obteve sucesso.

Williams continuou trabalhando com teoria da complexidade na pós-graduação e nos anos seguintes. Em 2010, quatro anos após concluir seu doutorado, ele apresentou um resultado marcante — um pequeno passo, mas o maior em décadas, rumo à solução da questão mais famosa da ciência da computação teórica , sobre a natureza dos problemas complexos. Esse resultado consolidou a reputação de Williams, e ele passou a escrever dezenas de outros artigos sobre diferentes tópicos da teoria da complexidade.

P versus PSPACE não era uma delas. Williams era fascinado pelo problema desde que o encontrou pela primeira vez na faculdade. Ele até complementou seu currículo de ciência da computação com cursos de lógica e filosofia, buscando inspiração em outras perspectivas sobre tempo e espaço, sem sucesso.

"Isso sempre esteve na minha cabeça", disse Williams. "Eu simplesmente não conseguia pensar em nada interessante o suficiente para dizer sobre isso."

No ano passado, ele finalmente encontrou a oportunidade que estava esperando.

A história do novo resultado de Williams começou com o progresso em uma questão diferente sobre memória na computação: quais problemas podem ser resolvidos com espaço extremamente limitado? Em 2010, o pioneiro teórico da complexidade Stephen Cook e seus colaboradores inventaram uma tarefa, chamada problema de avaliação de árvore , que provaram ser impossível para qualquer algoritmo com um orçamento de espaço abaixo de um limite específico. Mas havia uma brecha. A prova se baseava na mesma suposição de senso comum que Paul e seus colegas haviam feito décadas antes: algoritmos não podem armazenar novos dados em um espaço que já está cheio.

Por mais de uma década, os teóricos da complexidade tentaram fechar essa brecha. Então, em 2023, o filho de Cook, James , e um pesquisador chamado Ian Mertz a escancaram, desenvolvendo um algoritmo que resolveu o problema da avaliação de árvores usando muito menos espaço do que qualquer um imaginava ser possível. A prova do pai de Cook presumia que bits de dados eram como pedrinhas que precisam ocupar lugares separados na memória de um algoritmo. Mas acontece que essa não é a única maneira de armazenar dados. "Podemos, na verdade, pensar nessas pedrinhas como coisas que podemos espremer um pouco umas sobre as outras", disse Beame.

O algoritmo de Cook e Mertz despertou a curiosidade de muitos pesquisadores, mas não estava claro se ele tinha alguma aplicação além do problema de avaliação de árvores. "Ninguém percebeu o quão central ele é para o tempo versus espaço em si", disse Wigderson.

Ryan Williams foi a exceção. Na primavera de 2024, um grupo de alunos fez uma apresentação sobre o artigo de Cook e Mertz como projeto final em uma aula que ele ministrava. O entusiasmo deles o inspirou a examiná-lo mais de perto. Assim que o fez, uma ideia lhe veio à mente. O método de Cook e Mertz, ele percebeu, era, na verdade, uma ferramenta de uso geral para reduzir o uso do espaço. Por que não usá-lo para alimentar uma nova simulação universal que conectasse tempo e espaço — como a projetada por Hopcroft, Paul e Valiant, mas melhor?

Esse resultado clássico era uma maneira de transformar qualquer algoritmo com um determinado orçamento de tempo em um novo algoritmo com um orçamento de espaço ligeiramente menor. Williams percebeu que uma simulação baseada em pedrinhas macias tornaria o uso de espaço do novo algoritmo muito menor — aproximadamente igual à raiz quadrada do orçamento de tempo do algoritmo original. Esse novo algoritmo, com eficiência de espaço, também seria muito mais lento, portanto, a simulação provavelmente não teria aplicações práticas. Mas, do ponto de vista teórico, era nada menos que revolucionário.

Durante 50 anos, pesquisadores presumiram que era impossível melhorar a simulação universal de Hopcroft, Paul e Valiant. A ideia de Williams — se funcionasse — não apenas quebraria o recorde deles, como o destruiria.

"Pensei nisso e pensei: 'Bem, isso simplesmente não pode ser verdade'", disse Williams. Ele deixou o argumento de lado e só voltou a ele naquele dia fatídico de julho, quando tentou encontrar a falha no argumento e falhou. Depois de perceber que não havia falha, passou meses escrevendo e reescrevendo a prova para torná-la o mais clara possível.

No final de fevereiro, Williams finalmente colocou o artigo finalizado online . Cook e Mertz ficaram tão surpresos quanto todos os outros. "Tive que dar uma longa caminhada antes de fazer qualquer outra coisa", disse Mertz.

Valiant teve uma prévia da melhora de Williams em seu resultado de décadas atrás durante seu trajeto matinal. Há anos, ele leciona na Universidade Harvard, bem perto do escritório de Williams no MIT. Eles já se conheciam, mas não sabiam que moravam no mesmo bairro até se encontrarem no ônibus em um dia nevado de fevereiro, algumas semanas antes do resultado ser divulgado. Williams descreveu sua prova para Valiant, que ficou surpreso e prometeu enviar seu artigo.

“Fiquei muito, muito impressionado”, disse Valiant. “Se você obtiver qualquer resultado matemático que seja o melhor em 50 anos, você deve estar fazendo algo certo.”

Com sua nova simulação, Williams provou um resultado positivo sobre o poder computacional do espaço: algoritmos que usam relativamente pouco espaço podem resolver todos os problemas que exigem um tempo um pouco maior. Então, usando apenas algumas linhas de matemática, ele inverteu a situação e provou um resultado negativo sobre o poder computacional do tempo: pelo menos alguns problemas não podem ser resolvidos a menos que se use mais tempo do que espaço. Esse segundo resultado, mais restrito, está em linha com o que os pesquisadores esperavam. A parte estranha é como Williams chegou lá, primeiro provando um resultado que se aplica a todos os algoritmos, independentemente dos problemas que eles resolvam.

"Ainda tenho dificuldade em acreditar", disse Williams. "Parece bom demais para ser verdade."

Em termos qualitativos, o segundo resultado de Williams pode soar como a solução há muito buscada para o problema P versus PSPACE. A diferença é uma questão de escala. P e PSPACE são classes de complexidade muito amplas, enquanto os resultados de Williams trabalham em um nível mais refinado. Ele estabeleceu uma lacuna quantitativa entre o poder do espaço e o poder do tempo, e para provar que PSPACE é maior que P, os pesquisadores terão que aumentar essa lacuna muito, muito.

Esse é um desafio assustador, semelhante a abrir uma rachadura na calçada com um pé-de-cabra até que ela fique tão larga quanto o Grand Canyon. Mas talvez seja possível chegar lá usando uma versão modificada do procedimento de simulação de Williams, que repete a etapa principal várias vezes, economizando um pouco de espaço a cada vez. É como uma maneira de aumentar repetidamente o comprimento do seu pé-de-cabra — faça-o grande o suficiente e você poderá abrir qualquer coisa. Essa melhoria repetida não funciona com a versão atual do algoritmo, mas os pesquisadores não sabem se essa é uma limitação fundamental.

"Pode ser um gargalo definitivo, ou pode ser um gargalo de 50 anos", disse Valiant. "Ou pode ser algo que talvez alguém consiga resolver na semana que vem."

Se o problema for resolvido na próxima semana, Williams vai se arrepender. Antes de escrever o artigo, ele passou meses tentando, sem sucesso, estender seu resultado. Mas mesmo que tal extensão não seja possível, Williams está confiante de que mais exploração espacial certamente levará a algo interessante — talvez ao progresso em um problema totalmente diferente.

“Nunca consigo provar precisamente as coisas que quero provar”, disse ele. “Mas, muitas vezes, o que provo é muito melhor do que eu queria.”

Nota do editor: Scott Aaronson é membro do conselho consultivo da Quanta Magazine.

História original reimpressa com permissão da Quanta Magazine , uma publicação editorialmente independente da Fundação Simons cuja missão é aumentar a compreensão pública da ciência cobrindo desenvolvimentos e tendências de pesquisa em matemática e ciências físicas e biológicas.