Un estudiante descubre el potencial para acelerar todo Internet tras desentra?ar un rompecabezas inform¨¢tico de 40 a?os

En la actualidad, el vertiginoso mundo de la inform¨¢tica avanza constantemente. Un contexto donde los descubrimientos suelen llegar en forma de grandes lanzamientos y sofisticados dispositivos, a veces los hitos m¨¢s impactantes nacen de la propia curiosidad y del pensamiento de cualquier usuario. As¨ª fue como Andrew Krapivin, un estudiante estadounidense de la Universidad Rutgers, se top¨® con la soluci¨®n de un rompecabezas matem¨¢tico que hab¨ªa desconcertado a expertos durante cuatro d¨¦cadas. Aunque su hallazgo a¨²n no tiene aplicaciones inmediatas, s¨ª que podr¨ªa sentar las bases para acelerar el funcionamiento de Internet y otros sistemas inform¨¢ticos en el futuro.

?C¨®mo sucedi¨® el descubrimiento de Andrew Krapivin?

Todo comenz¨® cuando Krapivin accedi¨® a un art¨ªculo acad¨¦mico que exploraba un concepto cl¨¢sico en ciencias de la computaci¨®n: las tablas hash. Unas estructuras de datos que permiten asociar claves con valores, como si se tratasen de directorios inteligentes capaces de encontrar con rapidez informaci¨®n almacenada. ?stas, son esenciales para funciones como b¨²squedas, almacenamiento y eliminaci¨®n de datos, y han sido objeto de mejoras constantes en los ¨²ltimos a?os.

El estadounidense, interesado en reducir el consumo de memoria, intent¨® minimizar el tama?o de las ¡°flechas virtuales¡± que conectan claves y valores en estas tablas. Sin embargo, detect¨® que esto no era posible sin modificar por completo la estructura de las propias tablas hash. Fue entonces, mientras reflexionaba sobre el problema, cuando se acerc¨® a una antigua conjetura formulada en 1985 por el influyente cient¨ªfico inform¨¢tico Andrew Yao.

Yao hab¨ªa planteado que, bajo ciertas condiciones, el m¨¦todo m¨¢s eficiente para encontrar informaci¨®n en una tabla hash es recorrer de forma aleatoria los espacios vac¨ªos. Un proceso conocido como ¡®sondeo uniformizador¡¯ y que se consideraba ¨®ptimo en situaciones l¨ªmite. En su modelo, Yao asum¨ªa que el tiempo de ejecuci¨®n para encontrar un espacio vac¨ªo no superaba un valor x, que representaba el estado de ocupaci¨®n de la tabla.

Lo revolucionario en la aproximaci¨®n de Krapivin fue reemplazar ese valor x por el cuadrado del logaritmo (log x)?. Un cambio que lejos de ser un simple ajuste, supuso el dise?o de una tabla hash completamente nueva. Posteriorme?nte, trabajando con los investigadores Mart¨ªn Fa?rach-Colton y William Kuszmaul, expertos en estructuras conocidas como ¡°objetos flecha¡±, Krapivin demostr¨® que su tabla basada en el logaritmo cuadrado ofrece la forma ¨®ptima conocida hasta ahora para ubicar un elemento o espacio libre.

A d¨ªa de hoy es demasiado pronto para traducir este avance en aplicaciones pr¨¢cticas, pero los expertos coinciden en que este descubrimiento podr¨ªa ser la semilla de nuevas soluciones algor¨ªtmicas. En un campo donde los milisegundos importan, acabar de esta forma con d¨¦cadas de teor¨ªa establecida puede que signifique el primer paso hacia una nueva era en la inform¨¢tica. Y todo, sin olvidarnos, gracias a la mirada curiosa de un estudiante.

Sigue el canal de MeriStation en Twitter. Tu web de videojuegos y de entretenimiento, para conocer todas las noticias, novedades y ¨²ltima hora sobre el mundo del videojuego, cine, series, manga y anime. Avances, an¨¢lisis, entrevistas, tr¨¢ileres, gameplays, podcasts y mucho m¨¢s. ?Suscr¨ªbete! Si est¨¢s interesado en licenciar este contenido, pincha aqu¨ª.