Em um Artigo de 1985o cientista da computação Andrew Yaoque ganharia o prêmio AM Turing, afirmou que, entre as mesas de hash com um conjunto específico de propriedades, a melhor maneira de encontrar um elemento individual ou um ponto vazio é apenas passar por possíveis pontos aleatoriamente – uma abordagem conhecida como sondagem uniforme. Ele também afirmou que, no pior cenário, onde você está procurando o último local aberto restante, você nunca pode fazer melhor do que x. Por 40 anos, a maioria dos cientistas da computação assumiu que a conjectura de Yao era verdadeira.
Krapivin não foi retido pela sabedoria convencional pela simples razão de que ele não tinha conhecimento disso. “Fiz isso sem saber sobre a conjectura de Yao”, disse ele. Suas explorações com pequenas dicas levaram a um novo tipo de mesa de hash – uma que não depende de sondagem uniforme. E para esta nova tabela de hash, o tempo necessário para as piores consultas e inserções é proporcional a (log x)2—Mar mais rápido que x. Este resultado contradiz diretamente a conjectura de Yao. Farach-Colton e Kuszmaul ajudaram Krapivin a mostrar que (log x)2 é o destacado e imbatível para a classe popular de tabelas de hash que Yao havia escrito.
“Este resultado é bonito, pois aborda e resolve um problema tão clássico”, disse Guy Blelloch de Carnegie Mellon.
“Não é apenas que eles refutassem (a conjectura de Yao), eles também encontraram a melhor resposta possível para sua pergunta”, disse Sepehr Assad da Universidade de Waterloo. “Poderíamos ter ido mais 40 anos antes de sabermos a resposta certa.”
Além de refutar a conjectura de Yao, o novo artigo também contém o que muitos consideram um resultado ainda mais surpreendente. Refere-se a uma situação relacionada, embora um pouco diferente: em 1985, Yao analisou não apenas os piores tempos para consultas, mas também no tempo médio tomado em todas as perguntas possíveis. Ele provou que as tabelas de hash com certas propriedades – incluindo aquelas que são rotuladas como “gananciosas”, o que significa que novos elementos devem ser colocados no primeiro local disponível – nunca poderiam alcançar um tempo médio melhor do que o log do que o log do que x.
Farach-Colton, Krapivin e Kuszmaul queriam ver se o mesmo limite também se aplicava às mesas de hash não-greedas. Eles mostraram que não forneceu um contra-exemplo, uma tabela de hash sem grade com um tempo médio de consulta que é muito, muito melhor do que log x. Na verdade, não depende de x de forma alguma. “Você recebe um número”, disse Farach-Colton, “algo que é apenas uma constante e não depende de quão cheia a tabela de hash”. O fato de você poder alcançar um tempo médio constante de consulta, independentemente da plenitude da tabela de hash, foi totalmente inesperado – mesmo aos próprios autores.
Os resultados da equipe podem não levar a aplicativos imediatos, mas isso não é o que importa, disse Conway. “É importante entender melhor esses tipos de estruturas de dados. Você não sabe quando um resultado como esse desbloqueará algo que permite fazer melhor na prática. ”
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.
