A nova prova comprime dramaticamente o espaço necessário para a computação
Surpreendente novo trabalho Bucks 50 anos de suposições sobre as compensações entre o espaço de computação e o tempo
Era uma vez que os computadores encheram salas inteiras, lendo números de fitas giratórias e agitando -as através de fios para fazer cadeias de aritmética básica. Hoje eles deslizam nos bolsos, apresentando uma pequena fração de segundo o que costumava levar horas. Mas, mesmo quando as batatas fritas encolhem e ganham velocidade, os teóricos estão lançando a pergunta de quanto espaço de computação podemos colocar em uma máquina até o pouco o suficiente para fazer o trabalho.
Essa investigação está no centro da complexidade computacional, uma medida dos limites de quais problemas podem ser resolvidos e a que custo no tempo e no espaço. Por quase 50 anos os teóricos acreditavam que, se resolver um problema t etapas, também deve precisar aproximadamente t Bits de memória – os 0s e 1s que uma máquina usa para gravar informações. (Tecnicamente, essa equação era t/registro(t), mas para os números envolvendo log (t) é tipicamente insignificante.) Se uma tarefa envolver 100 etapas, por exemplo, você esperaria precisar de pelo menos 100 bits, o suficiente para registrar diligentemente cada etapa. Pensa -se que o uso de menos bits exigisse mais etapas – como alfabetizar seus livros, trocando -os um por um na prateleira, em vez de puxá -los todos para fora e remodelá -los. Mas em uma descoberta surpreendente descrita nesta semana no Simpósio da ACM sobre teoria da computação em Praga, o cientista da computação do Instituto de Tecnologia de Massachusetts, Ryan Williams, descobriu que qualquer problema solucionável no tempo t precisa apenas sobre √t Bits de memória: um cálculo de 100 etapas pode ser comprimido e resolvido com algo na ordem de 10 bits. “Este resultado mostra que a intuição anterior é completamente falsa”, diz Williams. “Eu pensei que deveria haver algo errado (com a prova) porque isso é extremamente inesperado.”
A inovação depende de uma “redução”, um meio de transformar um problema em outro que pode parecer não relacionado, mas é matematicamente equivalente. Com reduções, embalar uma mala mapeia para determinar um orçamento mensal: o tamanho da sua mala representa seu orçamento total, peças de roupa correspondem a despesas em potencial e decidir cuidadosamente quais roupas podem caber é como alocar seu orçamento. Resolver um problema resolveria diretamente o outro. Essa idéia está no centro do resultado de Williams: qualquer problema pode ser transformado em um que você pode resolver reutilizando inteligentemente o espaço, enfiando habilmente as informações necessárias em apenas um número de bits de raiz quadrada. Assim, o problema original deve ser solucionável com este contêiner compacto.
Sobre apoiar o jornalismo científico
Se você está gostando deste artigo, considere apoiar nosso jornalismo premiado por assinando. Ao comprar uma assinatura, você está ajudando a garantir o futuro das histórias impactantes sobre as descobertas e idéias que moldam nosso mundo hoje.
“Esse progresso é inacreditável”, diz Mahdi Cheraghchi, cientista da computação da Universidade de Michigan. “Antes desse resultado, havia problemas que você poderia resolver em um certo período de tempo, mas muitos pensaram que você não poderia fazê -lo com tão pouco espaço”. A descoberta de Williams, acrescenta, é “um passo na direção certa que não sabíamos como tomar”.
Embora os computadores tenham continuado diminuindo, nossa compreensão teórica de sua eficiência explodiu, sugerindo que a restrição real não é quanta memória temos, mas com sabor que a usamos.