Perché i piccioni a riposo sono al centro della teoria della complessità

La versione originale di questa storia è apparsa su Quanta Magazine .

Si dice che un uccello in mano vale due in un cespuglio, ma per gli informatici, due uccelli in una tana sono ancora meglio. Questo perché questi uccelli che coabitano sono i protagonisti di un teorema matematico apparentemente semplice chiamato principio della tana. È facile riassumerlo in una breve frase: se sei piccioni si annidano in cinque tane, almeno due di loro devono condividere una tana. Tutto qui, questo è tutto.

"Il principio del piccione è un teorema che strappa un sorriso", ha detto Christos Papadimitriou , informatico teorico alla Columbia University. "È un fantastico spunto di conversazione."

Ma il principio del "casellaggio" non è solo per gli uccelli. Anche se sembra dolorosamente semplice, è diventato uno strumento potente per i ricercatori impegnati nel progetto centrale dell'informatica teorica: mappare le connessioni nascoste tra diversi problemi.

Il principio dei piccioni si applica a qualsiasi situazione in cui gli oggetti siano assegnati a categorie e il numero degli oggetti superi quello delle categorie. Ad esempio, implica che in uno stadio di calcio gremito con 30.000 posti a sedere, alcuni spettatori debbano avere la stessa password di quattro cifre, o PIN, per le loro carte di credito. In questo caso, i piccioni sono i tifosi di calcio e i buchi sono i 10.000 PIN possibili, da 0000 a 9999. Si tratta di un numero di possibilità inferiore al numero totale di persone, quindi alcune persone devono avere le stesse cifre.

Questa dimostrazione è notevole non solo per la sua semplicità, ma anche per ciò che omette. Molti metodi matematici per dimostrare l'esistenza di qualcosa sono "costruttivi", ovvero mostrano anche come trovarlo. Le dimostrazioni "non costruttive", come quelle basate sul principio della casella, non hanno questa proprietà. Nell'esempio dello stadio di calcio, sapere che alcune persone devono avere gli stessi PIN non vi dirà quali siano. Potete sempre passare tra gli spalti e chiedere a ogni persona a turno. Ma esiste un modo più semplice?

Domande come questa, sul modo più efficiente per risolvere i problemi, sono al centro di una branca dell'informatica nota come teoria della complessità computazionale. I teorici della complessità studiano tali questioni raggruppando i problemi in classi basate su determinate proprietà condivise. A volte il primo passo verso una svolta è semplicemente definire una nuova classe per unire problemi che i ricercatori non avevano precedentemente studiato insieme.

Questo è ciò che accadde negli anni '90, quando Papadimitriou e altri teorici della complessità iniziarono a studiare nuove classi di problemi , in cui l'obiettivo era trovare qualcosa che dovesse esistere in virtù del principio del "piccionaio" o di un'altra dimostrazione non costruttiva. Questa linea di ricerca ha portato a importanti progressi in diversi campi dell'informatica, dalla crittografia alla teoria algoritmica dei giochi .

A gennaio 2020, Papadimitriou rifletteva sul principio della cella di piccione da 30 anni. Rimase quindi sorpreso quando una conversazione scherzosa con un collaboratore abituale li portò a una semplice modifica del principio che non avevano mai considerato: cosa succede se ci sono meno piccioni che buchi? In tal caso, qualsiasi disposizione di piccioni deve lasciare dei buchi vuoti. Di nuovo, sembra ovvio. Ma invertire il principio della cella di piccione ha delle conseguenze matematiche interessanti?

Potrebbe sembrare che questo principio della "casella vuota" sia semplicemente quello originale con un altro nome. Ma non è così, e il suo carattere leggermente diverso lo ha reso uno strumento nuovo e proficuo per la classificazione dei problemi computazionali.

Per comprendere il principio della casella vuota, torniamo all'esempio della carta di credito, trasposto da uno stadio di calcio a una sala concerti con 3.000 posti a sedere, un numero inferiore al totale dei possibili PIN a quattro cifre. Il principio della casella vuota prevede che alcuni possibili PIN non siano affatto rappresentati. Se si vuole trovare uno di questi PIN mancanti, tuttavia, non sembra esserci modo migliore che chiedere semplicemente a ogni persona il proprio PIN. Finora, il principio della casella vuota è identico al suo equivalente più noto.

La differenza sta nella difficoltà di verificare le soluzioni. Immaginate che qualcuno affermi di aver trovato due persone specifiche nello stadio di calcio che hanno lo stesso PIN. In questo caso, corrispondente allo scenario originale della casella vuota, esiste un modo semplice per verificare tale affermazione: basta verificare con le due persone in questione. Ma nel caso della sala concerti, immaginate che qualcuno affermi che nessuna persona ha il PIN 5926. In questo caso, è impossibile verificare senza chiedere a tutti gli spettatori qual è il loro PIN. Questo rende il principio della casella vuota molto più problematico per i teorici della complessità.

Due mesi dopo aver iniziato a riflettere sul principio della casella vuota, Papadimitriou lo sollevò in una conversazione con un futuro studente di dottorato. Lo ricorda vividamente, perché si rivelò essere la sua ultima conversazione di persona con qualcuno prima dei lockdown dovuti al Covid-19. Chiuso in casa nei mesi successivi, si occupò delle implicazioni del problema per la teoria della complessità. Alla fine, lui e i suoi colleghi pubblicarono un articolo sui problemi di ricerca la cui soluzione è garantita grazie al principio della casella vuota. Erano particolarmente interessati ai problemi in cui le caselle vuote sono abbondanti, ovvero dove superano di gran lunga il numero dei piccioni. In linea con una tradizione di acronimi poco maneggevoli nella teoria della complessità, chiamarono questa classe di problemi APEPP, per "principio della casella vuota polinomiale abbondante".

Uno dei problemi di questo corso è stato ispirato da una famosa dimostrazione di 70 anni fa del pioniere dell'informatica Claude Shannon . Shannon dimostrò che la maggior parte dei problemi computazionali deve essere intrinsecamente difficile da risolvere, usando un argomento basato sul principio della casella vuota (anche se lui non lo chiamava così). Eppure, per decenni, gli informatici hanno cercato, senza successo, di dimostrare che specifici problemi siano davvero difficili. Come lo smarrimento del PIN di una carta di credito, i problemi difficili devono esistere, anche se non siamo in grado di identificarli.

Storicamente, i ricercatori non hanno mai pensato al processo di ricerca di problemi complessi come a un problema di ricerca a sua volta analizzabile matematicamente. L'approccio di Papadimitriou, che raggruppava tale processo con altri problemi di ricerca legati al principio della casella vuota, aveva un sapore autoreferenziale caratteristico di gran parte dei lavori recenti nella teoria della complessità: offriva un nuovo modo di ragionare sulla difficoltà di dimostrare la difficoltà computazionale.

"Si sta analizzando il compito della teoria della complessità utilizzando la teoria della complessità", ha affermato Oliver Korten , ricercatore alla Columbia.

Korten era il potenziale studente con cui Papadimitriou aveva discusso del principio del "casello vuoto" poco prima della pandemia. Arrivò alla Columbia per lavorare con Papadimitriou e, durante il primo anno di dottorato, dimostrò che la ricerca di problemi computazionali complessi era intimamente legata a tutti gli altri problemi dell'APEPP . In senso matematico specifico, qualsiasi progresso su questo singolo problema si tradurrà automaticamente in progressi su una serie di altri che informatici e matematici studiano da tempo, come la ricerca di reti prive di sottostrutture semplici .

L'articolo di Korten ha immediatamente attirato l'attenzione di altri ricercatori. "Sono rimasto piuttosto sorpreso quando l'ho visto", ha detto Rahul Santhanam , teorico della complessità all'Università di Oxford. "È incredibilmente entusiasmante". Da allora, lui e altri hanno sfruttato la scoperta di Korten per dimostrare una serie di nuovi risultati sulle connessioni tra difficoltà computazionale e casualità.

"C'è una ricchezza incredibile in questo", ha detto Papadimitriou. "Va fino in fondo a importanti problemi di complessità."

Articolo originale ripubblicato con autorizzazione di Quanta Magazine , una pubblicazione editorialmente indipendente della Simons Foundation, la cui missione è quella di migliorare la comprensione pubblica della scienza, occupandosi degli sviluppi e delle tendenze della ricerca in matematica, scienze fisiche e della vita.