Novo horizonte na pesquisa de algoritmos: prova mostra que “um pouco de memória pode ser mais poderoso do que muito tempo”

• Uma nova prova apresentada pelo cientista teórico da computação do MIT Ryan Williams mostra que a memória pode ser um recurso computacional mais poderoso do que o tempo
• O resultado rompe uma estagnação de 50 anos na relação entre complexidade de tempo e espaço e propõe uma forma de transformar qualquer algoritmo para usar menos memória
• O núcleo da prova é a ideia de generalizar a simulação com economia de espaço para reduzir o uso de espaço de um algoritmo ao nível da raiz quadrada do tempo
• Com isso, houve avanço na demonstração quantitativa da diferença entre as classes PSPACE e P, além de abrir a possibilidade de provas com separações ainda maiores
• Especialistas avaliam o feito como um “avanço surpreendente e ponto de partida para uma nova exploração”, e consideram que o resultado pode ajudar a resolver outros problemas difíceis da computação teórica

---

One Small Step for Space, One Giant Leap for Complexity

Visão geral da nova prova de Ryan Williams

• No verão de 2024, Ryan Williams, do MIT, percebeu ao revisar sua prova que uma ideia que ele achava ser um erro na verdade era válida
• Ele propôs um procedimento geral para transformar qualquer algoritmo de modo que possa ser executado com menos memória
• Isso permitiu demonstrar que alguns problemas não podem ser resolvidos dentro de limites restritos de tempo

Tempo e espaço: dois recursos da computação

• Todo algoritmo usa tempo e memória (espaço)
• Antes, acreditava-se que, ao resolver certos problemas, o espaço era proporcional ao tempo
• A prova de Williams estabelece matematicamente que o espaço pode ser mais poderoso do que o tempo

Origem e história da computação teórica

• Juris Hartmanis e Richard Stearns estabeleceram, nos anos 1960, as definições de complexidade de tempo/espaço
• Eles lançaram as bases para classificar problemas em classes de complexidade de acordo com os recursos necessários para resolvê-los
• P representa problemas solucionáveis em tempo razoável, enquanto PSPACE representa problemas solucionáveis com quantidade adequada de memória

O primeiro avanço: a técnica de simulação de 1975

• Hopcroft, Paul e Valiant desenvolveram um procedimento universal de simulação capaz de converter qualquer algoritmo para usar um pouco menos espaço
• Esse foi o primeiro passo para esclarecer a relação entre tempo e espaço, mas depois o progresso esbarrou em limites
• Acreditava-se que não seria possível avançar além disso por causa da premissa de que dados não podem ocupar o mesmo espaço ao mesmo tempo

O ponto de virada: Squishy Pebbles

• Em 2010, o pioneiro da teoria da complexidade Stephen Cook e seus colegas conceberam o problema de avaliação de árvore - Pebbles and Branching Programs for Tree Evaluation e provaram que a tarefa é impossível para algoritmos com orçamento de espaço abaixo de certo limite
  • Mas havia uma brecha. A prova se baseava na mesma suposição intuitiva usada décadas antes por Paul e seus colegas
  • Ou seja, que um algoritmo não pode armazenar novos dados em um espaço já cheio
  • Por mais de 10 anos, teóricos da complexidade tentaram fechar essa brecha
• James Cook, filho de Stephen Cook, e Ian Mertz publicaram em 2023 um algoritmo para o problema de avaliação de árvore que rompe essa suposição anterior Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
• Eles propuseram um novo modelo de representação em que dados na memória podem se sobrepor fisicamente
• Essa abordagem se tornou a chave para superar os limites das simulações anteriores

O salto decisivo de Williams

• Depois de conhecer a técnica de Cook-Mertz a partir da apresentação de estudantes, Williams teve a ideia de aplicá-la à simulação universal
• A nova simulação pode reduzir a exigência de espaço de um algoritmo ao nível da raiz quadrada do tempo
• Em fevereiro de 2025, ele publicou o artigo final no arXiv, recebendo grande elogio da comunidade acadêmica

O que esse resultado significa

• A prova não demonstra diretamente que PSPACE > P, mas é um avanço decisivo que cria uma “brecha” nessa direção
• Se no futuro esse procedimento puder ser aplicado repetidamente para ampliar essa separação, será possível chegar mais perto da resolução do problema P vs PSPACE
• Isso pode se tornar a pista inicial para resolver um dos problemas mais antigos da ciência da computação

Um desfecho marcante

• Williams relembrou o resultado desta forma:
  “Eu não consegui provar exatamente o que realmente queria provar, mas o que acabei provando foi ainda melhor do que eu queria.”

[nunojay]

....Hã?

[GN⁺]

Comentários do Hacker News

• Tirando a parte nebulosa, uma máquina de Turing com múltiplas fitas que roda em tempo t pode ser simulada usando espaço O(sqrt(t log t)) (normalmente levando mais tempo do que t) Simulating Time With Square-Root Space
  • É uma pena que os artigos da Quanta misturem linguagem poética ou exagerada demais em matemática e acabem gerando mal-entendidos. No artigo da Quanta, dizem que “certas tarefas exigiam uma quantidade de espaço proporcional ao tempo de execução”, mas nem mesmo olhando para a hierarquia de complexidade surge uma intuição geral assim. Não dá para construir uma intuição ampla a partir de algo limitado a “alguns algoritmos”
  • Não sei se é gentileza demais com o leitor, mas achei meio ofensivo a Quanta explicar a classe de complexidade P apenas como “todos os problemas que podem ser resolvidos em um tempo razoável”, sem nem usar o termo polynomial
• Há uma passagem assim no “Camel Book”, que carrega a filosofia do Perl: “Se você está sem memória, pode comprar mais, mas se está sem tempo, não há o que fazer”. Gosto dele por ser simplesmente um livro divertido
  • Também acho que essa frase tem dois lados. Um programa que precisa de mais memória do que o computador tem simplesmente não pode rodar agora; por outro lado, mesmo que demore muito, ainda dá para executar, então tempo também é um recurso importante
• A vitória das tabelas de consulta com valores pré-computados. Antigamente eu achava que, se fosse possível armazenar centralmente todas as operações a ponto de não precisar de processador, a velocidade de processamento poderia ser revolucionária (embora exista o problema difícil separado de fazer buscas rápidas)
  • Quando comecei a trabalhar com sistemas de armazenamento, uma vez sugeri a ideia de pré-computar e guardar todos os blocos de 4 KB, e fiquei chocado quando me apontaram que o número de blocos únicos de 4 KB é maior que o número de átomos no universo
  • O algoritmo HashLife faz algo parecido, de forma Turing-completa, no Conway’s Game of Life. Acho fascinante que ele consiga saltar para estados futuros pré-computando trechos, mesmo lidando com estados muito complexos e variados
  • A piada é que não há problema algum em também fazer cache do próprio lookup de retrieval
  • Isso já é implementado na prática em distribuição de software com cache em nível de comunidade, isto é, software pré-compilado. A barreira tradicional de abrir mão de recursos da linguagem porque não dá para compilar com eficiência também pode ser superada com compilação paralela na nuvem e cache global. Se compilar uma vez no lançamento, todo mundo pode usar
  • Na linha de “se todas as operações estivessem armazenadas centralmente, talvez nem precisássemos de processador”, a ideia seria memorizar até o próprio histórico de buscas
• Como o estilo da Quanta é muito poético, fica difícil entender se esta pesquisa realmente se aplica a computadores práticos ou se é um cenário puramente teórico. Fico curioso se isso significa que, ao usar mais memória, o computador fica mais lento
• Trabalho com programação de gráficos raster há muito tempo, e o uso de lookup tables acabou virando algo natural para mim. Recentemente, desenvolvi uma ferramenta de servidor que coloca várias formas prévias no banco de dados e usa resultados otimizados a cada consulta. É um padrão simples e intuitivo. Não foi algo aprendido especificamente com um professor do MIT, mas um jeito de trabalhar que fui adquirindo na prática; então é gratificante ver uma prova matemática de que isso faz sentido. Às vezes muito know-how algorítmico realmente nasce da experiência dos praticantes (ex.: algoritmo de winding number)
  • Os ganhos que tenho obtido ultimamente ao otimizar jogos vêm todos de tratar lookup tables de acordo com o contexto. Não precisam ser apenas arrays estáticos para serem lookup tables; dados que mudam um pouco ao longo do tempo também podem ser usados assim. Isso me fez enxergar mais o lado de processar trabalho na GPU, e há bastante eficiência em uma estrutura onde tabelas antes geradas estaticamente em compilação ou em runtime passam a ter só partes alteradas durante a execução e são enviadas para a GPU como texturas. A fronteira do que chamar de lookup table fica borrada
• Parece intuitivo que espaço (memória) pode representar muito mais resultados do que tempo. Em uma fita de comprimento n, você pode escrever durante O(n) tempo, mas se a fita é binária existem 2^n configurações possíveis para esse comprimento. Se o espaço for bem usado, ele parece dar muito mais poder de representação do que o tempo
  • Minha intuição: uma única célula pode armazenar resultados intermediários de centenas de cálculos. Se você não puder armazenar esses resultados intermediários e tiver de recalcular a mesma coisa toda vez, a eficiência cai muito. Situações com 0% de acerto de cache são raríssimas; na maioria dos casos dá para ganhar eficiência usando espaço. Em contrapartida, é difícil substituir o espaço de centenas de células com uma única unidade de tempo, e nas arquiteturas atuais de computação SIMD infinita é impossível
  • A suposição de acesso aleatório à memória em O(1) é tratada como óbvia demais, mas na prática o custo de acesso cresce até O(n^(1/3)) à medida que o computador aumenta. Dá para sentir isso claramente em datacenters. Acho que era um modelo diferente de UMA
  • Como P ≠ PSPACE ainda não foi provado, é uma área em que demonstrar matematicamente é mais difícil do que parece pela intuição
  • Por outro lado, embora isso seja verdade, em problemas difíceis de paralelizar (ex.: alternating machine PTIME=PSPACE) o espaço pode não trazer um ganho tão grande. No artigo, o salto de t/log t para sqrt(t log t) é revolucionário, mas deve haver limites substanciais que nem a paralelização infinita consegue superar
  • Na prática, depende das características da tarefa. Quando o acesso ao armazenamento é muito mais lento do que uma atribuição, às vezes recalcular é mais rápido
• A “relação inversa” entre tempo e espaço pode ser explicada como o fenômeno em que, ao restringir um recurso, você não consegue necessariamente obter o ótimo do outro. Por exemplo, em algoritmos de ordenação, quando há três restrições — tempo, espaço e estabilidade —, exigir estabilidade pode piorar a eficiência de tempo ou de espaço. Até hoje não existe uma ordenação estável tão rápida e com tão pouco uso de memória quanto as ordenações instáveis
• Pessoalmente, gosto do estilo dos artigos da Quanta Magazine. Eles ampliam o horizonte não só para cientistas da computação, mas também para o público geral interessado na área. A visão panorâmica e o tom acessível acabam servindo de gatilho para novas perspectivas e ideias
• Compartilha links para palestras e artigos de Ryan Williams
• Se uma máquina de Turing de fita única recebe como entrada um inteiro binário N e tenta escrever N vezes o valor 1 à direita da fita, parece que ela precisaria de espaço N em tempo N. Então fico me perguntando como isso poderia ser simulado com menos espaço que N. Também queria entender que relação isso tem com computadores reais, já que, pela estrutura da máquina de Turing, não dá para saltar para posições arbitrárias da fita
  • Máquinas de Turing com múltiplas fitas são muito mais rápidas do que as de fita única, e o “espaço” de que se fala aqui é o espaço temporário de trabalho, excluindo entrada e saída
  • O artigo trata principalmente de problemas de decisão, em que a saída necessária tem apenas 1 bit. Se a saída tiver N bits, a explicação é que isso é essencialmente equivalente a juntar N problemas de decisão