Gli informatici vogliono sapere quanti passaggi richiede un determinato algoritmo. Advert esempio, qualsiasi algoritmo locale in grado di risolvere il problema del router con solo due colori deve essere incredibilmente inefficiente, ma è possibile trovare un algoritmo locale molto efficiente se è consentito usarne tre.
Al discorso a cui Bernshteyn ha partecipato, il relatore ha discusso di queste soglie per diversi tipi di problemi. Una delle soglie, si rese conto, somigliava molto a una soglia che esisteva nel mondo della teoria descrittiva degli insiemi: riguardava il numero di colori richiesti per colorare certi grafici infiniti in modo misurabile.
A Bernshteyn sembrò qualcosa di più di una coincidenza. Non si tratta solo del fatto che anche gli informatici sono come i bibliotecari, che accantonano i problemi in base all’efficienza con cui funzionano i loro algoritmi. Non si tratta solo del fatto che questi problemi potevano essere scritti anche in termini di grafici e colorazioni.
Forse, pensò, i due scaffali avevano più cose in comune. Forse la connessione tra questi due campi è andata molto, molto più in profondità.
Forse tutti i libri e i loro scaffali erano identici, solo scritti in lingue various e avevano bisogno di un traduttore.
Aprendo la porta
Bernshteyn ha deciso di rendere esplicito questo collegamento. Voleva dimostrare che ogni algoritmo locale efficiente può essere trasformato in un modo misurabile secondo Lebesgue di colorare un grafo infinito (che soddisfa alcune importanti proprietà aggiuntive). Cioè, uno degli scaffali più importanti dell’informatica è equivalente a uno degli scaffali più importanti della teoria degli insiemi (in alto nella gerarchia).
Ha iniziato con la classe dei problemi di rete della lezione di informatica, concentrandosi sulla loro regola generale: l’algoritmo di ogni dato nodo utilizza informazioni solo sul suo quartiere locale, indipendentemente dal fatto che il grafico abbia mille o un miliardo di nodi.
Per funzionare correttamente, tutto ciò che l’algoritmo deve fare è etichettare ciascun nodo in un dato quartiere con un numero univoco, in modo che possa registrare informazioni sui nodi vicini e fornire istruzioni su di essi. È abbastanza facile da fare in un grafico finito: basta dare a ogni nodo del grafico un numero diverso.
