Computerwetenschappers willen weten hoeveel stappen een bepaald algoritme nodig heeft. Elk lokaal algoritme dat het routerprobleem met slechts twee kleuren kan oplossen, moet bijvoorbeeld ongelooflijk inefficiënt zijn, maar het is mogelijk een zeer efficiënt lokaal algoritme te vinden als je er drie mag gebruiken.
Tijdens de lezing die Bernshteyn bijwoonde, besprak de spreker deze drempels voor verschillende soorten problemen. Een van de drempels, besefte hij, leek veel op een drempel die bestond in de wereld van de beschrijvende verzamelingenleer: over het aantal kleuren dat nodig is om bepaalde oneindige grafieken op een meetbare manier te kleuren.
Voor Bernshteyn voelde het als meer dan toeval. Het was niet alleen zo dat computerwetenschappers ook bibliothecarissen zijn, die problemen op de plank leggen op basis van hoe efficiënt hun algoritmen werken. Het was niet alleen zo dat deze problemen ook in termen van grafieken en kleuringen konden worden geschreven.
Misschien, dacht hij, hadden de twee boekenplanken meer gemeen dan dat. Misschien ging de verbinding tussen deze twee velden veel dieper.
Misschien waren alle boeken en hun planken identiek, alleen in verschillende talen geschreven – en hadden ze een vertaler nodig.
Het openen van de deur
Bernshteyn wilde dit verband expliciet maken. Hij wilde laten zien dat elk efficiënt lokaal algoritme kan worden omgezet in een Lebesgue-meetbare manier om een oneindige grafiek in te kleuren (die aan enkele aanvullende belangrijke eigenschappen voldoet). Dat wil zeggen: een van de belangrijkste planken van de informatica is gelijk aan een van de belangrijkste planken van de verzamelingenleer (hoog in de hiërarchie).
Hij begon met de klasse van netwerkproblemen uit de lezing over computerwetenschappen, waarbij hij zich concentreerde op hun overkoepelende regel: dat het algoritme van elk knooppunt alleen informatie gebruikt over de lokale omgeving, ongeacht of de grafiek duizend of een miljard knooppunten heeft.
Om goed te kunnen werken hoeft het algoritme alleen maar elk knooppunt in een bepaalde buurt te voorzien van een uniek nummer, zodat het informatie over nabijgelegen knooppunten kan registreren en er instructies over kan geven. Dat is eenvoudig genoeg om te doen in een eindige grafiek: geef gewoon elk knooppunt in de grafiek een ander nummer.
