Essas são restrições bastante rigorosas, por isso não era óbvio que a memória extra poderia ser útil. Mas, para sua surpresa, Buhrman e Cleve mostraram que, se você ajustar os pedaços da maneira certa, poderá realmente obter uma força computacional extra de uma memória completa.
“Isso foi chocante para todos”, disse Loff, que era estudante de graduação no grupo de Buhrman na época, trabalhando na pergunta da memória com seu colega estudante Florian Speelman. A equipe logo estendeu o resultado a uma classe ainda maior de problemas e publicou seus resultados combinados em 2014.
Eles nomearam a nova computação catalÃtica da estrutura, emprestando um termo da quÃmica. “Sem o catalisador, a reação não teria prosseguido”, disse Raghunath Tewarium teórico da complexidade no Instituto Indiano de Tecnologia, Kanpur. “Mas o próprio catalisador permanece inalterado.”
Não muito longe da árvore
Um pequeno grupo de pesquisadores continuou a desenvolver computação catalÃtica, mas ninguém tentou aplicá -lo 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 da computação catalÃtica dependiam da memória extra e completa muito grande. Encolher 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 uma maneira de adaptar essas técnicas para reutilizar a memória em um algoritmo de avaliação de árvores. O nome dele era James CookE 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é havia trabalhado nisso na pós -graduação, embora ele se concentrasse principalmente em assuntos completamente não relacionados. Quando encontrou o artigo de computação catalÃtica original em 2014, James estava prestes a se formar e deixar a academia para engenharia de software. Mas, mesmo quando ele se estabeleceu em seu novo emprego, ele continuou pensando em computação catalÃtica.
“Eu tive que entender e ver o que poderia ser feito”, disse ele.
Durante anos, James Cook mexeu com uma abordagem catalÃtica do problema de avaliação de árvores em seu tempo livre. Ele deu uma palestra sobre seu progresso em um simpósio de 2019 em homenagem ao de seu pai trabalho inovador na teoria da complexidade. Após a palestra, ele foi abordado por um estudante de pós -graduação nomeado Ian Mertzque se apaixonou pela computação catalÃtica cinco anos antes depois de aprender sobre isso como um jovem graduado impressionável.
“Era como um cenário de impressão de um pássaro”, disse Mertz.
Fotografia: Revista Stefan Grosser/Quanta
Cook e Mertz uniram forças, e seus esforços logo valeram a pena. Em 2020, eles criaram um algoritmo Isso resolveu o problema de avaliação de árvores com menos memória do que um mÃnimo necessário conjeturado pelo cozinheiro ancião e McKenzie – embora estivesse pouco abaixo desse limite. Ainda assim, isso foi suficiente para cobrar na aposta de US $ 100; Convenientemente para os cozinheiros, metade dele ficou 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 na avaliação de árvores de L. foi inativo, mas não saiu.
Em 2023, Cook e Mertz saÃram com um Algoritmo aprimorado Isso usou muito menos memória – caramente mais do que o máximo permitido para problemas em L. Muitos pesquisadores agora suspeitam que a avaliação de árvores esteja em L, afinal, e que uma prova é apenas uma questão de tempo. Os teóricos da complexidade podem precisar de uma abordagem diferente do problema P versus L.
Enquanto isso, os resultados de Cook e Mertz têm interesse galvanizado na computação catalÃtica, com novos trabalhos explorando Conexões à aleatoriedade e os efeitos de permitir um alguns erros Ao redefinir a memória completa em seu estado original.
“Não terminamos de explorar o que podemos fazer com essas novas técnicas”, disse McKenzie. “Podemos esperar ainda mais surpresas.”
História original reimpresso com permissão de Quanta revistaAssim, uma publicação editorialmente independente do Fundação Simons cuja missão é melhorar a compreensão pública da ciência, cobrindo os desenvolvimentos e tendências da pesquisa em matemática e ciências fÃsicas e da vida.
