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: het betrof het aantal kleuren dat nodig was om bepaalde oneindige grafieken op een meetbare manier te kleuren.
Voor Bernshteyn leek het meer dan toeval. Het is niet alleen zo dat computerwetenschappers net bibliothecarissen zijn, die problemen afwijzen op basis van hoe efficiënt hun algoritmen werken. Het is niet alleen zo dat deze problemen ook in termen van grafieken en kleuren kunnen worden geschreven.
Misschien, dacht hij, hadden de twee planken meer gemeen. 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.
De deur openen
Bernshteyn besloot dit verband expliciet te maken. Hij wilde bewijzen dat elk efficiënt lokaal algoritme kan worden omgezet in een Lebesgue-meetbare manier om een oneindige grafiek in te kleuren (die aan enkele belangrijke aanvullende eigenschappen voldoet). Dat wil zeggen, een van de belangrijkste planken in de informatica is gelijk aan een van de belangrijkste planken in de verzamelingenleer (hoger in de hiërarchie).
Hij begon met de klasse netwerkproblemen van de computerwetenschappen, waarbij hij zich concentreerde op hun algemene regel: het algoritme van een bepaald knooppunt gebruikt alleen informatie over de lokale omgeving, ongeacht of de grafiek duizend of een miljard knooppunten heeft.
Om goed te werken hoeft het algoritme alleen maar elk knooppunt in een bepaalde buurt te voorzien van een uniek nummer, zodat het informatie over aangrenzende knooppunten kan vastleggen en er instructies over kan geven. Het is eenvoudig genoeg om te doen in een voltooide grafiek: geef gewoon elk knooppunt in de grafiek een ander nummer.
