En Papel de 1985el informático Andrew Yaoque continuaría ganando el premio AM Turing, afirmó que entre las tablas hash con un conjunto específico de propiedades, la mejor manera de encontrar un elemento individual o un lugar vacío es simplemente pasar por posibles puntos al azar, un enfoque conocido como sondeo uniforme. También declaró que, en el peor de los casos, donde estás buscando el último lugar abierto restante, nunca puedes hacerlo mejor que incógnita. Durante 40 años, la mayoría de los científicos informáticos asumieron que la conjetura de Yao era cierta.
Krapivin no fue retenida por la sabiduría convencional por la simple razón de que no lo sabía. “Hice esto sin saber sobre la conjetura de Yao”, dijo. Sus exploraciones con pequeños punteros condujeron a un nuevo tipo de mesa hash, una que no dependía de un sondeo uniforme. Y para esta nueva tabla hash, el tiempo requerido para las consultas e inserciones de peores casos es proporcional a (log incógnita)2—Far más rápido que incógnita. Este resultado contradice directamente la conjetura de Yao. Farach-Colton y Kuszmaul ayudaron a Krapivin a mostrar eso (log incógnita)2 es el óptimo e inmejorable con destino a la popular clase de tablas hash sobre la que Yao había escrito.
“Este resultado es hermoso porque aborda y resuelve un problema tan clásico”, dijo Guy Blelloch de Carnegie Mellon.
“No es solo que refutaron [Yao’s conjecture]también encontraron la mejor respuesta posible a su pregunta ”, dijo Sepehr Assadi de la Universidad de Waterloo. “Podríamos haber pasado otros 40 años antes de que supiéramos la respuesta correcta”.
Además de refutar la conjetura de Yao, el nuevo artículo también contiene lo que muchos consideran un resultado aún más sorprendente. Se refiere a una situación relacionada, aunque ligeramente diferente, en 1985, Yao no solo miró los peores momentos de las consultas, sino también en el tiempo promedio tomado en todas las consultas posibles. Probó que las tablas hash con ciertas propiedades, incluidas las que están etiquetadas como “codiciosas”, lo que significa que se deben colocar nuevos elementos en el primer lugar disponible, nunca podrían lograr un tiempo promedio mejor que log incógnita.
Farach-Colton, Krapivin y Kuszmaul querían ver si ese mismo límite también se aplicaba a las tablas de hash no greedia. Demostraron que no proporcionó un contraejemplo, una mesa de hash no verde con un tiempo de consulta promedio que es mucho, mucho mejor que log incógnita. De hecho, no depende de incógnita en absoluto. “Obtienes un número”, dijo Farach-Colton, “algo que es solo una constante y no depende de cuán llena sea la tabla hash”. El hecho de que pueda lograr un tiempo de consulta promedio constante, independientemente de la plenitud de la tabla hash, fue totalmente inesperado, incluso para los mismos autores.
Los resultados del equipo pueden no conducir a ninguna aplicación inmediata, pero eso no es todo lo que importa, dijo Conway. “Es importante comprender mejor este tipo de estructuras de datos. No sabe cuándo un resultado como este desbloqueará algo que le permite hacerlo mejor en la práctica ”.
Historia original reimpreso con permiso de Revista cuantauna publicación editorialmente independiente del Fundación Simons cuya misión es mejorar la comprensión pública de la ciencia cubriendo los desarrollos de la investigación y las tendencias en matemáticas y las ciencias físicas y de la vida.