Computerwetenschappers willen weten hoeveel stappen een algoritme neemt. Elk lokaal algoritme dat het routerprobleem met slechts twee kleuren kan oplossen, is bijvoorbeeld zeer inefficiënt, maar zeer efficiënte lokale algoritmen kunnen worden gevonden als u drie kleuren mag gebruiken.
Tijdens de lezing die Bernshteyn bijwoonde, bespraken sprekers drempels voor verschillende soorten problemen. Een van de drempels, besefte hij, leek veel op een drempel die bestaat in de wereld van de beschrijvende verzamelingenleer: over het aantal kleuren dat nodig is om een bepaalde oneindige grafiek op een meetbare manier te kleuren.
Voor Bernshteyn voelde dit als meer dan alleen toeval. Het zijn niet alleen computerwetenschappers die, net als bibliothecarissen, problemen uitsluiten op basis van hoe efficiënt hun algoritmen werken. Niet alleen dat, deze vragen kunnen ook in grafische en kleurvorm worden geschreven.
Misschien, dacht hij, hadden de twee boekenplanken meer gemeen dan dat. Misschien is de verbinding tussen deze twee velden veel dieper.
Misschien zijn alle boeken en planken hetzelfde, alleen geschreven in een andere taal – en is er een vertaler nodig.
Het openen van de deur
Bernshteyn probeerde dit verband expliciet te maken. Hij wilde laten zien dat elk lokaal efficiënt algoritme kan worden omgezet in een schaalbare Lebesgue-manier om oneindige grafieken in te kleuren (die aan verschillende aanvullende belangrijke eigenschappen voldoet). Dat wil zeggen, een van de belangrijkste planken in de informatica is gelijk aan een van de belangrijkste planken in de verzamelingenleer (de hoogste in de hiërarchie).
Hij begon met een klasse netwerkproblemen van de universiteit voor computerwetenschappen, waarbij hij zich concentreerde op de algemene regel van dergelijke problemen: elk knooppuntalgoritme gebruikt alleen informatie over de lokale omgeving, ongeacht of de grafiek duizend of een miljard knooppunten heeft.
Om goed te kunnen werken hoeft het algoritme elk knooppunt in een bepaalde buurt alleen maar te voorzien van een uniek nummer, zodat het informatie kan vastleggen over nabijgelegen knooppunten en instructies kan geven over die knooppunten. Dat is eenvoudig genoeg om te doen in een eindige grafiek: geef gewoon elk knooppunt in de grafiek een ander nummer.
