Cientista da computação propõe que algoritmos podem exigir menos memória para resolver problemas

Essa discussão faz parte do campo da complexidade computacional — a área que estuda os limites do que pode ser resolvido por algoritmos e os custos associados em tempo e espaço.

A suposição tradicional é que, se a resolução de um problema exige t etapas, então seriam necessários aproximadamente t bits de memória. Por exemplo, para uma tarefa com 100 etapas, estimava-se a necessidade de ao menos 100 bits, o suficiente para registrar cada passo.

No entanto, segundo Ryan Williams, cientista da computação no MIT, qualquer problema resolvível em tempo t pode ser solucionado usando apenas uma quantidade de memória proporcional à raiz quadrada de t bits. Isso significa que uma computação com 100 etapas poderia ser executada com algo em torno de apenas 10 bits.

A descoberta se baseia em uma técnica conhecida como redução — um método que transforma um problema em outro aparentemente distinto, mas matematicamente equivalente. Com isso, é possível reaproveitar espaço de forma inteligente, comprimindo a informação necessária a uma fração proporcional à raiz quadrada do número de etapas.

A conclusão sugere que o verdadeiro obstáculo pode não estar na quantidade de memória disponível, mas na maneira como ela é utilizada.