Essas são restrições bastante rigorosas, então não era óbvio que a memória extra pudesse ser útil. Mas, para surpresa deles, Buhrman e Cleve mostraram que se você ajustar os bits de maneira certa, realmente é possível obter mais poder computacional de uma memória completa.
“Isso foi uma surpresa para todos”, disse Loff, que era estudante de pós-graduação no grupo de Buhrman na época, trabalhando na questão da memória com seu colega estudante Florian Speelman. A equipe logo estendeu o resultado para uma classe ainda maior de problemas e publicou seus resultados combinados em 2014.
Eles chamaram o novo framework de computação catalítica, emprestando um termo da química. “Sem o catalisador, a reação não teria prosseguido”, disse Raghunath Tewari, um teórico da complexidade no Instituto Indiano de Tecnologia, Kanpur. “Mas o próprio catalisador permanece inalterado.”
Não Tão Distante da Árvore
Um pequeno grupo de pesquisadores continuou a desenvolver a computação catalítica ainda mais, mas ninguém tentou aplicá-la ao problema de avaliação de árvores que inicialmente inspirou a busca de Koucký. Para esse problema, a questão em aberto restante era se uma pequena quantidade de memória poderia ser usada para armazenamento e computação simultaneamente. Mas as técnicas de computação catalítica dependiam da memória extra, completa, sendo muito grande. Diminua essa memória e as técnicas não funcionam mais.
Ainda assim, um jovem pesquisador não pôde deixar de se perguntar se havia um meio de adaptar essas técnicas para reutilizar a memória em um algoritmo de avaliação de árvores. Seu nome era James Cook, e para ele o problema de avaliação de árvores era pessoal: Stephen Cook, o lendário teórico da complexidade que o inventou, é seu pai. James até mesmo trabalhou nisso na pós-graduação, embora principalmente focado em assuntos completamente não relacionados. Na época em que ele encontrou o artigo original sobre computação catalítica em 2014, James estava prestes a se formar e deixar a academia para engenharia de software. Mas mesmo enquanto se estabelecia em seu novo emprego, ele continuava pensando sobre computação catalítica.
“Eu precisava entender e ver o que poderia ser feito”, disse ele.
Durante anos, James Cook mexeu com uma abordagem catalítica para o problema de avaliação de árvores em seu tempo livre. Ele apresentou uma palestra sobre seu progresso em um simpósio de 2019 em homenagem ao trabalho inovador de seu pai na teoria da complexidade. Após a palestra, foi abordado por um estudante de pós-graduação chamado Ian Mertz, que se apaixonou pela computação catalítica cinco anos antes, após conhecê-la como um jovem universitário influenciável.
“Foi como um cenário de impressão de passarinho bebê”, disse Mertz.
Cook e Mertz uniram forças, e seus esforços logo deram frutos. Em 2020, eles conceberam um algoritmo que resolveu o problema de avaliação de árvores com menos memória do que um mínimo necessário conjecturado pelo Cook mais velho e McKenzie — embora tenha ficado apenas um pouco abaixo desse limite. Mesmo assim, foi o suficiente para ganhar a aposta de $100; convenientemente para os Cooks, metade dela permaneceu na família.
Mas ainda havia trabalho a fazer. Os pesquisadores começaram a estudar a avaliação de árvores porque parecia que poderia finalmente fornecer um exemplo de um problema em P que não está em L. Em outras palavras, um problema relativamente fácil que não pode ser resolvido usando muito pouca memória. O novo método de Cook e Mertz usou menos memória do que qualquer outro algoritmo de avaliação de árvores, mas ainda usou significativamente mais do que qualquer algoritmo para um problema em L. A avaliação de árvores estava em baixa, mas não fora.
Em 2023, Cook e Mertz lançaram um algoritmo aprimorado que usava muito menos memória — pouco mais do que o máximo permitido para problemas em L. Muitos pesquisadores agora suspeitam que a avaliação de árvores está em L afinal, e que uma prova é apenas questão de tempo. Teóricos da complexidade podem precisar de uma abordagem diferente para o problema P versus L.
Enquanto isso, os resultados de Cook e Mertz despertaram o interesse na computação catalítica, com novos trabalhos explorando conexões com a aleatoriedade e os efeitos de permitir alguns erros ao redefinir a memória completa para seu estado original.
“Ainda não terminamos de explorar o que podemos fazer com essas novas técnicas”, disse McKenzie. “Podemos esperar ainda mais surpresas.”
