Los informáticos quieren saber cuántos pasos requiere un algoritmo determinado. Por ejemplo, cualquier algoritmo local que pueda resolver el problema del enrutador con sólo dos colores debe ser increíblemente ineficiente, pero es posible encontrar un algoritmo local muy eficiente si se le permite usar tres.
En la charla a la que asistió Bernshteyn, el orador discutió estos umbrales para diferentes tipos de problemas. Se dio cuenta de que uno de los umbrales se parecía mucho a un umbral que existía en el mundo de la teoría descriptiva de conjuntos: sobre el número de colores necesarios para colorear ciertos gráficos infinitos de una manera mensurable.
Para Bernshteyn, esto parecía más que una coincidencia. No se trata sólo de que los científicos informáticos también sean como bibliotecarios, archivando problemas en función de la eficiencia con la que funcionan sus algoritmos. No era sólo que estos problemas también pudieran escribirse en términos de gráficos y colores.
Quizás, pensó, las dos estanterías tuvieran más en común que eso. Quizás la conexión entre estos dos campos fuera mucho, mucho más profunda.
Quizás todos los libros y sus estantes eran idénticos, sólo que estaban escritos en diferentes idiomas y necesitaban un traductor.
Abriendo la puerta
Bernshteyn se propuso hacer explícita esta conexión. Quería demostrar que todo algoritmo local eficiente se puede convertir en una forma medible de Lebesgue de colorear un gráfico infinito (que satisface algunas propiedades adicionales importantes). Es decir, uno de los estantes más importantes de la informática es equivalente a uno de los estantes más importantes de la teoría de conjuntos (en lo alto de la jerarquía).
Comenzó con la clase de problemas de red de la conferencia de ciencias de la computación, centrándose en su regla general: que el algoritmo de cualquier nodo utiliza información sólo sobre su vecindad local, ya sea que el gráfico tenga mil nodos o mil millones.
Para ejecutarse correctamente, todo lo que el algoritmo tiene que hacer es etiquetar cada nodo en un vecindario determinado con un número único, de modo que pueda registrar información sobre los nodos cercanos y dar instrucciones sobre ellos. Eso es bastante fácil de hacer en un gráfico finito: simplemente asigne a cada nodo del gráfico un número diferente.