Los científicos de la computación se interesan por determinar la cantidad de pasos que requiere un algoritmo determinado. Por ejemplo, cualquier algoritmo local que pueda resolver el problema del enrutamiento con solo dos colores resulta increíblemente ineficiente, pero es posible encontrar un algoritmo local muy eficiente si se permite el uso de tres colores.
En una conferencia a la que asistió Bernshteyn, el ponente discutió estos umbrales para diferentes tipos de problemas. Uno de estos umbrales, se dio cuenta Bernshteyn, se asemejaba mucho a un umbral existente en el mundo de la teoría de conjuntos descriptiva, relacionado con el número de colores necesarios para colorear ciertos grafos infinitos de manera medible.
A Bernshteyn le pareció más que una coincidencia. No se trataba solo de que los científicos de la computación, al igual que los bibliotecarios, organizan los problemas según la eficiencia de sus algoritmos. Tampoco era simplemente que estos problemas pudieran expresarse en términos de grafos y coloraciones.
Quizás, pensó, las dos “bibliotecas” tenían más en común que eso. Quizás la conexión entre estos dos campos era mucho más profunda.
Tal vez todos los “libros” y sus “estanterías” fueran idénticos, simplemente escritos en diferentes idiomas y necesitados de un traductor.
Abriendo la Puerta
Bernshteyn se propuso hacer explícita esta conexión. Su objetivo era demostrar que cada algoritmo local eficiente puede transformarse en una forma Lebesgue-medible de colorear un grafo infinito (que cumple con propiedades adicionales importantes). En otras palabras, una de las “estanterías” más importantes de la informática es equivalente a una de las “estanterías” más importantes de la teoría de conjuntos (en lo alto de la jerarquía).
Comenzó con la clase de problemas de red presentados en la conferencia de informática, centrándose en su regla fundamental: que el algoritmo de cada nodo utiliza información solo de su vecindad local, ya sea que el grafo tenga mil nodos o mil millones.
Para funcionar correctamente, todo lo que el algoritmo tiene que hacer es etiquetar cada nodo en una vecindad dada con un número único, para poder registrar información sobre los nodos cercanos y darles instrucciones. Esto es relativamente sencillo en un grafo finito: basta con asignar a cada nodo del grafo un número diferente.
