Esse resultado clássico foi uma maneira de transformar qualquer algoritmo com um determinado orçamento de tempo em um novo algoritmo com um orçamento espacial um pouco menor. Williams viu que uma simulação baseada em seixos mole tornaria o uso espacial do novo algoritmo muito menor – basicamente igual à raiz quadrada do orçamento de tempo do algoritmo original. Esse novo algoritmo com eficiência espacial também seria muito mais lento, portanto a simulação provavelmente não teria aplicações práticas. Mas, do ponto de vista teórico, era nada menos que revolucionário.
Por 50 anos, os pesquisadores assumiram que era impossível melhorar a simulação universal de Hopcroft, Paul e Valiant. A idéia de Williams – se funcionasse – não apenas vencesse o recorde deles -, o demoliria.
“Eu pensei sobre isso, e fiquei tipo, ‘Bem, isso simplesmente não pode ser verdadeiro’”, disse Williams. Ele o deixou de lado e não voltou a ele até aquele dia fatídico em julho, quando tentou encontrar a falha no argumento e falhou. Depois que ele percebeu que não havia falha, ele passou meses escrevendo e reescrevendo a prova para deixá -lo o mais claro possível.
No final de fevereiro, Williams finalmente Coloque o papel acabado online. Cook e Mertz ficaram tão surpresos quanto todos os outros. “Eu tive que dar uma longa caminhada antes de fazer qualquer outra coisa”, disse Mertz.
Valiant obteve uma prévia da melhoria de Williams em seu resultado de décadas durante seu trajeto matinal. Durante anos, ele ensinou na Universidade de Harvard, no final da estrada do escritório de Williams no MIT. Eles haviam se conhecer antes, mas não sabiam que moravam no mesmo bairro até que se esbarraram no ônibus em um dia nevado de fevereiro, algumas semanas antes do resultado ser público. Williams descreveu sua prova ao assustado Valiant e prometeu enviar ao longo de seu artigo.
“Fiquei muito, muito impressionado”, disse Valiant. “Se você obtiver algum resultado matemático que seja a melhor coisa em 50 anos, deve estar fazendo algo certo.”
Pspace: a fronteira final
Com sua nova simulação, Williams provou ser um resultado positivo sobre o poder computacional do espaço: algoritmos que usam relativamente pouco espaço podem resolver todos os problemas que exigem uma quantidade de tempo um pouco maior. Então, usando apenas algumas linhas de matemática, ele virou isso e provou um resultado negativo sobre o poder computacional do tempo: pelo menos alguns problemas não podem ser resolvidos, a menos que você use mais tempo que o espaço. Esse segundo resultado mais estreito está de acordo com o que os pesquisadores esperavam. A parte estranha é como Williams chegou lá, primeiro provando um resultado que se aplica a todos os algoritmos, independentemente dos problemas que eles resolvem.
“Ainda tenho dificuldade em acreditar”, disse Williams. “Parece bom demais para ser verdade.”
Williams usou a técnica de Cook e Mertz para estabelecer uma ligação mais forte entre o espaço e o tempo – o primeiro progresso nesse problema em 50 anos.Fotografia: Katherine Taylor para revista Quanta
Frulsed em termos qualitativos, o segundo resultado de Williams pode parecer a solução há muito procurada para o problema P versus o Pspace. A diferença é uma questão de escala. P e PSPACE são classes de complexidade muito amplas, enquanto os resultados de Williams funcionam em um nível mais fino. Ele estabeleceu uma lacuna quantitativa entre o poder do espaço e o poder do tempo e, para provar que o Pspace é maior que o P, os pesquisadores terão que tornar essa lacuna muito, muito mais ampla.
Esse é um desafio assustador, semelhante a um rachadouro na calçada com um pé de cabra até o Grande Canyon. Mas pode ser possível chegar lá usando uma versão modificada do procedimento de simulação de Williams que repete a etapa -chave muitas vezes, economizando um pouco de espaço a cada vez. É como uma maneira de aumentar repetidamente o comprimento do seu pé de cabra – faça com que seja grande o suficiente e você pode abrir qualquer coisa. Essa melhoria repetida não funciona com a versão atual do algoritmo, mas os pesquisadores não sabem se isso é uma limitação fundamental.
“Pode ser um gargalo melhor, ou pode ser um gargalo de 50 anos”, disse Valiant. “Ou pode ser algo que talvez alguém possa resolver na próxima semana.”
Se o problema for resolvido na próxima semana, Williams estará se chutando. Antes de escrever o jornal, ele passou meses tentando e deixando de estender seu resultado. Mas mesmo que essa extensão não seja possível, Williams está confiante de que mais exploração espacial deve liderar um lugar interessante – talvez progredir em um problema totalmente diferente.
“Eu nunca posso provar precisamente as coisas que quero provar”, disse ele. “Mas, muitas vezes, o que provo é muito melhor do que eu queria.”
Nota do editor: Scott Aaronson é membro da revista Quanta Conselho Consultivo.
História original reimpresso com permissão de Quanta revistauma 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.
