Tecnología
Un estudiante descubre el potencial para acelerar todo Internet tras desentrañar un rompecabezas informático de 40 años
Un intento por ahorrar memoria terminó resolviendo una incógnita informática sin respuesta desde 1985.
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 . 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. Posteriormente, trabajando con los investigadores Martín Farach-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í.