Cinquantamila.it La storia raccontata da Giorgio Dell'Arti

Si dice che in città ci troviamo sempre a pochi metri di distanza da un topo. Ma di questi tempi sembra più probabile trovarsi sempre a pochi metri di distanza da qualcuno che gioca a Candy Crush Saga. Attualmente è uno dei giochi più popolari su Facebook; è stato scaricato e installato su telefonini, tablet e computer più di mezzo miliardo di volte. Anche grazie a questo successo la società che lo sviluppa, Global King, è stata quotata di recente alla borsa di New York con un’offerta pubblica iniziale in cui l’azienda è stata valutata miliardi di dollari. Niente male per un giochino che consiste nello scambiare di posto coppie di caramelle per formare File di tre o più elementi identici.
Buona parte dell’attrattiva di Candy Crush deriva dalle strutture complesse che si nascondono dietro a un rompicapo apparentemente semplice. È un gioco che, sorprendentemente, si rivela di grande interesse anche per i ricercatori: ci aiuta a capire alcuni dei più importanti problemi aperti della matematica, nonché della sicurezza dei sistemi informatici.
Ho dimostrato di recente che Candy Crush è un rompicapo la cui soluzione è difficile dal punto di vista matematico. Per provare questo punto ho fatto ricorso a uno dei conceni più belli e importanti di tutta l’informatica teorica, la riduzione tra problemi.
L’idea consiste nel ricondurre, o appunto «ridurre», la soluzione di un problema a quella di un altro. Alle origini del concetto c’è il fatto che i programmi per computer sono versatili: possiamo usare lo stesso tipo di codice per risolvere più di un problema, addirittura se le variabili sono diverse. Se il problema da cui siamo partiti era difficile, quello a cui ci riconduciamo deve esserlo almeno altrettanto. Il secondo problema non può essere più facile, perché deve essere possibile risolvere il primo con un programma che risolve il secondo. E se mostriamo che vale anche l’inverso, che cioè anche il secondo problema si può ridurre al primo, allora c’è un senso in cui i due problemi hanno la stessa difficoltà e richiedono un tempo simile per essere risolti.
Determinare la difficoltà di un problema è un aspetto fondamentale della matematica, ma non si tratta solo di un interesse teorico. Se riusciamo a classificare un problema in base a quanto è difficile risolverlo sappiamo quanta potenza di calcolo dobbiamo dedicargli, e anche solo se vale la pena di provare a risolverlo. Da un certo punto di vista, considerare Candy Crush come un problema matematico può essere appassionante quanto giocarci.

Soluzioni difficili, verifiche facili
Nella nostra analisi di Candy Crush io e i miei colleghi siamo partiti dalla classe più famosa di problemi computazionalmente difficili, la cosiddetta NP; la sigla significa non deterministic polynomial lime, cioè «non deterministico polinomiale», dove il «polinomiale» si riferisce al tempo necessario per risolvere questi problemi. NP contiene tutti i problemi per i quali, se ne viene proposta una possibile soluzione, possiamo verificare rapidamente se è corretta, in un tempo non maggiore di una funzione polinomiale della dimensione del problema. Invece trovare la soluzione prima di tutto sembra computazionalmente arduo. Molti problemi matematici noti – come stabilire se una formula logica complessa si può soddisfare, o se un grafo si può colorare con un certo numero di colori in modo che nodi adiacenti abbiano colori diversi – appartengono a questa classe di problemi computazionalmente difficili.
Al di sotto della classe NP, in termini di complessità, abbiamo la classe P dei problemi computazionalmente «facili». Qui P sta semplicemente per «polinomiale». P contiene problemi come quello di ordinare un elenco o trovare un dato in un banca dati. Il tempo necessario a un programma efficiente per risolvere questo tipo di problemi è breve, addirittura nel peggiore dei casi. Matematicamente, il tempo di esecuzione di un problema in P è un polinomio che ha come variabile la «grandezza» del problema. Per esempio, un famoso algoritmo di ordinamento, BubbleSort, fa salire via via gli elementi più piccoli, come se fossero bolle che emergono in superficie. Questo procedimento richiede un tempo che cresce come il quadrato della lunghezza dell’elenco da ordinare. Se raddoppiamo la lunghezza dell’elenco, alla peggio l’algoritmo impiega un tempo quadruplo. Il caso peggiore è quello in cui all’inizio la lista è completamente invertita e ogni elemento deve incrociare ogni altro. Se l’elenco non è in questo ordine opposto, l’algoritmo finirà ancora più rapidamente.
Al di sopra di NP, come complessità, ci sono problemi estremamente difficili computazionalmente. Ce ne sono addirittura alcuni per cui il nostro modello computazionale usuale, quello che tutti i nostri computer adottano, è inadeguato. Sono problemi per cui non esiste un programma che sicuramente si arresta e fornisce una risposta. Questi esempi ricadono nella classe dei problemi cosiddetti indecidibili. Questa classe comprende problemi come quello di stabilire se un dato programma avrà termine oppure procederà all’infinito in qualche loop: il cosiddetto problema dell’arresto. Alan Turing, uno dei padri dell’informatica, dimostrò che il problema dell’arresto è indecidibile. Non esiste un programma che sia in grado di decidere se un altro programma si arresti e che, esso stesso, si arresti sicuramente: siamo quindi in presenza di un problema decisamente difficile, dal punto di vista computazionale.
NP è al confine tra facile e difficile. All’interno di NP abbiamo molti problemi impegnativi come quello di tracciare le rotte dei camion per consegnare spedizioni, organizzare i turni del personale di un ospedale o l’orario delle lezioni di una scuola. E si scopre che anche vincere a Candy Crush rientra in questa categoria. Ognuno di questi problemi si può ridurre a ognuno degli altri: da questo punto di vista sono tutti altrettanto difficili.
Purtroppo i migliori programmi che abbiamo per i problemi in NP hanno un tempo di esecuzione che cresce spettacolarmente al crescere delle dimensioni del problema. Sul mio PC ho un programma che impiega qualche ora a trovare i percorsi ottimali per dieci camion e a dimostrare che questa soluzione è la migliore possibile. Ma per 100 camion lo stesso programma ci metterebbe un tempo maggiore dell’età dell’universo. Dal punto di vista matematico, il tempo di esecuzione del mio programma è una funzione esponenziale della grandezza del problema.
E gli esponenziali diventano rapidamente enormi, come illustra la classica leggenda in cui un sultano garantisce al suo visir qualunque ricompensa desideri, e il visir chiede un chicco di grano per la prima casella di una scacchiera, e poi il doppio per ogni casella successiva. Ci sarà così un chicco sulla prima casella, due sulla seconda, quattro sulla terza e così via. Per tutte e 64 le caselle servirebbero 18.446.744.073.709.551.615 chicchi di grano, cioè più di 18 miliardi di miliardi. È la quantità di grano prodotta in tutto il mondo in alcuni secoli. Gli esponenziali, per poco che ci distraiamo, ci sovrastano inesorabili.
Sebbene la maggior parte degli informatici sia d’accordo con me sul fatto che i problemi NP sono al confine tra facile e difficile, per ogni specifico problema non c’è un modo per sapere con certezza da che parte sta. Gli attuali migliori programmi richiedono un tempo esponenziale per risolvere i problemi in NP. Ma non possiamo escludere che esista qualche algoritmo esotico in attesa di essere scoperto che risolverà in modo efficiente, in tempo polinomiale, i problemi in NP. (I matematici condensano questo dubbio con «P = NP?») Questo è proprio uno dei problemi aperti più famosi e importanti della matematica odierna. Il Clay Mathematics Institute offre addirittura un milione di dollari a chi troverà la risposta a questa domanda. Da quando è stato bandito, nel 2000, il premio non è stato ancora assegnato.
Nel sondaggio più recente sulla validità di P = NP, secondo l’83 per cento degli informatici P non è uguale a NP: ritengono cioè che non esistano algoritmi efficienti per risolvere i problemi in NP, né mai potranno esistere. Un altro sondaggio tra gli informatici è servito a decidere come chiamare i problemi difficili da risolvere quanto quelli in NP, che appartengano o meno a questa classe. Il nome scelto alla fine è stato il prosaico NP-difficili («NP-hard»). Ma il sondaggio ha mostrato un piacevole senso dell’umorismo: tra le proposte alternative ci sono state «NP-impractical» (NP-scomodi), «NP-tricky» (NP-complicati) e «NP-hard-ass» (NP-tosti).
L’idea della riduzione tra problemi è centrale per la questione P = NP. Se trovassimo un algoritmo che possa risolvere in modo efficiente certi specifici problemi in NP, potremmo anche risolvere in modo efficiente tutti gli altri problemi in NP. Il mondo sarebbe un posto diverso, se succedesse davvero. Dal lato positivo, vivremmo con un migliore gestione del tempo, con trasporti, voli e turni gestiti in modo ottimale, il che ci farebbe risparmiare (e vincere sempre a Candy Crush). D’altronde in altri ambiti, come la violazione di codici segreti, contiamo sul fatto che siano computazionalmente impegnativi, in modo che le nostre password e il nostro conto in banca siano al sicuro. La complessità computazionale può essere una benedizione e una iattura allo stesso tempo. Vogliamo che sia garantita la difficoltà di svolgere i calcoli con cui gli hacker potrebbero decifrare i messaggi, ma vogliamo anche poter cifrare facilmente gli stessi messaggi.
Questo esempio vi ricorda forse la definizione di NP: problemi in cui è facile verificare la soluzione ma è difficile trovarla. La crittografia si basa proprio sul fatto di porre barriere computazionali sulla strada dei malintenzionati. Se queste barriere scomparissero, il nostro mondo passerebbe seri guai.

Dietro al gioco
Per mostrare che Candy Crush è un problema matematicamente arduo, possiamo ridurci a esso da qualsiasi problema in NP. Per non complicarci troppo la vita, io e i miei colleghi siamo partiti dall’antesignano di tutti i problemi in NP, quello di trovare una soluzione a una formula logica. È detto problema della soddisfacibilità. Se avete mai affrontato un rompicapo logico, avete risolto un problema del genere: bisogna decidere quali proposizioni devono essere vere e quali false per soddisfare un insieme di formule logiche. L’inglese vive nella casa rossa. Il cane è dello spagnolo. Il norvegese vive accanto alla casa azzurra. La proposizione che lo spagnolo è proprietario della zebra deve essere vera o falsa?
Per ridurre un rompicapo logico a un problema di Candy Crush sfruttiamo lo stretto legame tra la logica e i circuiti elettrici. Qualsiasi formula logica si può rappresentare in modo semplice con un circuito elettrico. Dopotutto i computer non sono altro che un ammasso di porte logiche – AND, OR e NOT – collegate da cavi. Quindi basta far vedere che all’interno di una partita di Candy Crush possiamo costruire un circuito elettrico.
Prima di tutto ci serve una base su cui costruirlo. La base deve essere una disposizione neutra di caramelle che non interagiscono tra loro. Questa scacchiera di caramelle somiglia un po’ a un semaforo: nelle colonne pari alterniamo «fagioli» rossi e gocce al limone gialle, mentre in quelle dispari alterniamo pastiglie arancioni e gomme verdi. In questo modo, anche se una colonna scorre non si forma mai una catena di tre caramelle identiche.
In questa struttura inseriamo i componenti elettrici, che sono formati dai «grappoli» viola; li inseriamo in modo da spostare le altre caramelle, non da sovrapporvisi. Questi grappoli formano i cavi che trasmettono i segnali nel circuito, ed è anche possibile collegare più cavi per creare configurazioni più complesse quando serve. Se disponiamo un grappolo viola come segnale in ingresso del cavo a sinistra, creiamo una catena di tre grappoli viola. Questa catena scompare, come da regola base del gioco, e fa scendere le caramelle nelle colonne corrispondenti, propagando il segnale lungo il cavo. Alla fine, come output, sulla destra, comparirà un grappolo viola. È così che si trasmette un segnale nell’area di gioco.
Ci servono anche interruttori che possano essere usati dall’utente per decidere quali cavi sono attivi. Questi interruttori rappresentano la scelta se una proposizione della nostra formula booleana è posta come vera o falsa. L’utente può spostare in alto o in basso il grappolo viola centrale: questo spostamento attiva un segnale verso destra o verso sinistra.
Infine possiamo costruire porte logiche come AND, OR e NOT con altri gruppi di grappoli viola, a partire da questi componenti fondamentali. A questo punto dobbiamo solo collegare a queste porte logiche gli opportuni interruttori con cavi lunghi a sufficienza e avremo un circuito elettrico che simula la nostra porta logica. Il circuito elettrico ha un bit di output che rappresenta il valore di verità della formula.

Rappresentazione mediante rompicapi
Espresso in questi termini, giocare a Candy Crush consiste nel decidere quali interruttori commutare in modo che le porte logiche si attivino nel modo appropriato e il bit di output abbia il valore «vero». Riusciamo così a ridurre il problema di soddisfare una formula logica a quello di risolvere un problema di Candy Crush. E dato che soddisfare una formula logica è un problema difficile, lo deve essere anche risolvere un livello di Candy Crush.
Si può dimostrare anche l’inverso: possiamo cioè ridurre un problema di Candy Crush alla soddisfacibilità di una formula. Dob


biamo solo scrivere una sequenza di formule che descrivano un livello di Candy Crush. In sostanza, questa descrizione logica di Candy Crush già si trova nel programma. Quindi Candy Crush non è più difficile di ogni altro problema in NP, e giocarci è difficile quanto risolvere altri problemi in NP. Se avessimo un modo efficiente per giocare a Candy Crush, avremmo un modo dimostrabile per instradare con efficienza i camion, fissare i turni del personale o preparare gli orari delle lezioni. Viceversa, se sapessimo instradare camion, organizzare il personale o programmare lezioni con efficienza, avremmo un modo efficiente per giocare a Candy Crush. E la potenza del metodo della riduzione tra problemi.
La prossima volta che non riuscite a superare un livello di Candy Crush nel numero prescritto di mosse, vi potete consolare sapendo che è un problema matematicamente arduo da risolvere. Anzi, questa caratteristica può essere in parte ciò che rende così difficile smettere di giocare; se fosse facile come giocare a filetto, per esempio, non sarebbe altrettanto avvincente.
Alla base di tutto c’è l’idea elegante e basilare di riduzione tra problemi, che ha permesso agli informatici di semplificare il labirinto dei diversi problemi computazionali in un numero inferiore di classi fondamentali come P e NP, che formano nel complesso il cosiddetto zoo. Oggi nello zoo ci sono 500 classi di problemi, comprese quelle con nomi esotici come ∆₂P, LogFew, NEEE e P-close. (In caso vi fosse sfuggito, agli informatici piacciono gli acronimi.)
Nell’improbabile caso che si dimostri che P coincide con NP, il numero di classi nello zoo della complessità calerebbe molto. Numerose classi che riteniamo distinte verrebbero a coincidere. Se invece P non è uguale a NP, come ritiene la maggioranza degli informatici, lo zoo contiene molte classi distinte, anzi continua a crescere di dimensioni. Gli zoologi della complessità hanno introdotto anche nuove classi per descrivere la complessità dei problemi risolti con computer quantistici.
Il concetto della riduzione tra problemi offre una prospettiva affascinante per gli appassionati di Candy Crush. Sarà forse possibile mettere a buon uso i milioni di ore che le persone trascorrono risolvendo quadri di questo gioco? Sfruttando l’idea di riduzione tra problemi potremmo nascondere alcuni problemi computazionali di utilità concreta in questi rompicapi. Già ci sono alcuni problemi che traggono beneficio da questo tipo di interazione: ogni volta che dimostrate a un sito web che siete una persona e non un bot risolvendo un CAPTCHA (una di quelle onnipresenti immagini distorte di una parola o di un numero che dobbiamo inserire), la risposta aiuta Google a digitalizzare vecchi libri e articoli. Forse potremmo trovare un buon uso simile anche per Candy Crush.
I nostri studi su Candy Crush ci fanno provare un grande rispetto per questo passatempo apparentemente innocuo. In realtà ci aiuta ad approfondire uno dei più importanti problemi aperti della matematica, le cui implicazioni si estendono a molte applicazioni pratiche, come gli algoritmi di cifratura usati per tenere al sicuro i conti bancari. Potete provare a spiegare questa ampia visione delle cose al vostro capo, la prossima volta che vi sorprende a fare «ancora un livello e poi basta».

TOBY WALSH