Qualche mese fa vi avevo raccontato (qui, qui, e qui) delle dimostrazioni a conoscenza zero. Per chi non si ricorda e non ha voglia di tornare a leggere quei post, rispiego in poche parole di che cosa si tratta: è possibile “dimostrare” di conoscere la risposta a un problema complesso senza presentare la soluzione, ma rispondendo semplicemente a una serie di domande. Il punto fondamentale è che la risposta a ogni singola domanda non dà all’interlocutore nessuna informazione oltre al fatto che abbiamo risposto correttamente alla domanda. C’è sempre la possibilità che noi in realtà la risposta non la sappiamo e siamo stati fortunati: ma visto che l’interlocutore può farci quante domande vuole quella probabilità è piccola a piacere. Un esempio pratico. Sappiamo che ogni mappa planare può essere colorata con quattro colori in modo che due regioni confinanti non abbiano mai lo stesso colore. Ci sono però mappe per cui bastano tre colori: ma data una mappa dimostrare che questo è possibile è un problema spesso intrattabile. Immaginate però che io abbia trovato in qualche modo che una data mappa richiede solo tre colori, e ti voglia vendere la struttura. Voi non volete pagare senza aver visto la colorazione; io non voglio mostrarvi la colorazione prima di essere pagato altrimenti me la copiate e basta. Come si fa? Semplice (quando si sa il trucco)! Io scelgo a caso i tre colori con cui colorare la mappa e poi la copro. Tu mi indichi due regioni confinanti, io scopro solo quelle due regioni e mostro che hanno colore diverso. Certo: se avessi colorato la mappa a caso, avrei comunque mostrato due colori diversi in due casi su tre. Ma io posso fare una nuova colorazione, sempre casuale, e farti scegliere altre due regioni confinanti, diverse o le stesse non importa: di nuovo io ti mostro che hanno colori diversi. A questo punto la probabilità che io abbia avuto fortuna per due volte di fila scende a 1/9, e andando avanti calerà ancora di più; inoltre, proprio perché i colori in ciascuna richiesta sono casuali, non ho la possibilità di fare dei confronti.

Il problema di questo tipo di dimostrazioni è che sono interattive: tu domandi e io rispondo. Nel 1994 i crittografi Oded Goldreich e Yair Oren dimostrarono che è impossibile costruire una dimostrazione completatamente non interattiva che sia a conoscenza zero, come indicato sopra e definito formalmente da Shafi Goldwasser, Silvio Micali e Charles Rackoff. Fine della storia? A quanto pare no. Rahul Ilango ha messo sotto attento scrutinio la dimostrazione di Goldreich e Oren, e ha notato che dipende dal fatto che per avere una dimostrazione a conoscenza zero tu “sai” cosa io ti dirò (che cioè le due regioni sono colorate diversamente). Il termine tecnico per questo fatto è “esiste un simulatore”. Qui entra in scena Gödel, o meglio Ilango. Cosa succede se ti dico che esiste un simulatore, ma tu non sei in grado di trovarlo? Tecnicamente la dimostrazione di Goldreich e Oren regge: il simulatore esiste. Ma praticamente tu non puoi “sapere” qual è il simulatore, quindi la dimostrazione può essere non interattiva. In pratica (si fa per dire…) non diciamo più “questa mappa può essere colorata con tre colori”, ma “questa mappa può essere colorata con tre colori, se non esiste un metodo efficiente di dimostrare che la matematica non è contraddittoria”. Visto che non possiamo essere certi al 100% che la matematica non è contraddittoria, non possiamo essere certi al 100% che la dimostrazione non abbia un simulatore, e quindi abbiamo il diritto di non applicare il teorema di Goldreich e Oren. Se vi si è annodato il cervello, tranquilli: siete in buona compagnia.

Quello che mi lascia più stupito è lo sfruttare una limitazione a priori della conoscenza matematica per avanzare la conoscenza matematica stessa: un doppio salto mortale carpiato.