Nicc: sono malato, da un paio di giorni faccio spola fra divano, poltrona e letto. A leggere qualche cosa di intelligente faccio fatica e dopo il quinto DVD inizio ad avere gli occhi che bruciano. E allora decido, caro Ema, di buttar giù quel muro di pregiudizi che ho nei confronti dei “giochini scemi” (così li chiamo io) e di provare ad affrontare un SUDOKU! Eh sì, ci sono cascato anche io. Mi sono appassionato (speriamo che questa malattia non duri molto) al gioco del 9×9. 9 caselle, 9 quatrati, numeri dall’1 al 9… Dopo un po’ che giocavo, provando ogni volta a risolvere uno schema di maggiore difficoltà, mi son chiesto: come fa un matematico a sapere quanti numeri al minimo ci devono essere in uno schema vergine (meno numeri ci sono più difficile è il gioco) per far sì che sia ancora risolvibile? E ancora, benché sia un computer che sputi uno dopo l’altro questi schemini, come la matematica ci può aiutare a capire che cosa sta dietro al fantomatico Sudoku e perché piglia tanto?
Ema: Caro Nico, il mio PC è appoggiato su un tavolino della stazione di Zurigo, e alla sua destra, proprio a portata di mano, c’è una tazza di caffè fumante… quale momento migliore per scrivere sulla nostra nuova sezione del blog??
Allora, il sudoku.
La prima volta che ne ho visto uno ho effettivamente cominciato a risolverlo, ma poi ho perso la pazienza quasi subito: una volta che sai le regole e quei due-tre trucchetti, tipo scrivere in piccolo le cifre che ‘potrebbero’ andare in un quadratino, poi il resto diventava piuttosto ripetitivo, sostanzialmente un “esamina tutte le possibilità”, e siccome non ne vedevo la fine, mi ero chiesto: ma siamo sicuri che ‘sto coso ha una soluzione? C’è un modo (che non ti obblighi a farlo tutto) per sapere se un dato sudoku ha una soluzione? Quanti numeri bisogna dare al minimo perchè il sudoku sia fattibile?
Tutte queste domande sarebbero probabilmente risolte se qualcuno trovasse una tecnica veramente intelligente per fare il sudoku. Intendo: una vera strategia, che non ti obblighi ad esaminare tutte le caselle provando tutte le combinazioni.
Ho navigato un po’ sulla rete per trovare degli elementi, e ho scoperto che il sudoku è stato dimostrato essere NP-completo.
E voi, giustamente: “embe’?”.
E io, ostentando indifferenza: “Beh, vuol dire che se trovi una strategia veloce per farlo vinci un milione di dollari messi in palio dal Clay institute” ( www.claymath.org/millennium-problems/millennium-prize-problems ).
Ecco, vorrei tentare di spiegarvi perchè. Ci vorrà qualche riga: trattenete il fiato e allacciate le cinture.
Di solito, quando usiamo un computer, noi diamo alla macchina delle istanze (inputs) che lei interpreta ed elabora in base a precise istruzioni (il programma che si sta usando). Ad esempio: un programma per fare le addizioni elaborerà l’istanza [2,5] ritornando la risposta [7], mentre un programma per fare le moltiplicazioni la eleborerà diversamente, ritornando [10].
È anche chiaro che la stessa macchina con lo stesso programma può impiegare tempi diversi per elaborare istanze diverse. Per esempio, qualsiasi macchina con il programma che fa le moltiplicazioni ci metterà di più ad elaborare l’istanza [16346,8467] che ad elaborare [2,3]. Ci metteva di più anche il vostro cervello, quando alle scuole elementari gli avevano installato il programma per fare le moltiplicazioni, ricordate? In generale più è lunga l’istanza (più cifre hanno i numeri da moltiplicare), più tempo ci vorrà.
Per avere una stima di quanto ci si mette si studia bene il programma e, supponendo di avere un’istanza di una certa lunghezza, si guarda quanto è il lavoro che il nostro programma richiede alla macchina per risolverla. Per fare questo, si scompone il programma nelle ‘operazioni fondamentali’ che deve far compiere alla macchina. Ci si immagina che la macchina impieghi un certo tempo costante per eseguire un’operazione fondamentale. Così se so quante operazioni fondamentali dovrò eseguire e so quanto ci mette la mia macchina ad eseguire un’operazione fondamentale, potrò sapere quanto tempo ci mette la mia macchina a finire l’elaborazione. La quantità di operazioni che un programma richiede per elaborare un’istanza di lunghezza n è chiamata complessità del programma. Come spesso succede, la teoria della complessità computazionale
è stata sviluppata dai matematici addirittura prima che esistessero i computer – in realtà queste considerazioni si basano su un congegno immaginario, la ‘macchina di Turing’, ovvero una specie di computer ante litteram che Alan Turing (un personaggio cui spero dedicheremo qualche riga un’altra volta) nel 1936 non poteva fare altro che immaginare.
Si è quindi cominciato a classificare i problemi in base alla complessità del programma più ‘veloce’ che si conosca per risolverli. Per alcuni programmi il crescere della grandezza dell’istanza causa solo un accettabile incremento della quantità di operazioni necessarie. Per altri programmi, con l’aumentare della grandezza dell’istanza la quantità di operazioni richieste cresce in modo vertiginoso.
La classe dei problemi che si possono risolvere con programmi del primo tipo è chiamata classe P (“Polynomial time”: problemi la cui complessità è un polinomio in n). Vi è poi la classe NP, per “Nondeterministic Polynomial time”, e cioè (e questo è importante!) che l’unica maniera che si conosca per risolverli in tempo ragionevole è darli in pasto ad una macchina che sappia ‘tirare ad indovinare’.
Di NP fa parte per esempio il calcolo necessario per decifrare il vostro numero di carta di credito quando pagate via internet. Ovvero: non è impossibile farlo, ma anche i calcolatori più veloci esistenti ci metterebbero mesi/anni a svolgere il calcolo – ma a quel tempo la vostra carta di credito sarà già scaduta e inutilizzabile.
Naturalmente il fatto che non si conosca nessun metodo per risolvere velocemente questi problemi non vuol dire che tale metodo non ci sia. E inoltre ci sono alcuni di questi problemi che sono specialmente interessanti: se si riuscisse a risolvere uno di essi in modo veloce (mostrando che è in P), allora è dimostrato che si potrebbero risolvere in modo veloce tutti gli altri problemi in NP. Questi problemi speciali si chiamano problemi NP-completi.
Insomma: trovare una strategia ‘veloce’ per risolvere un problema NP-completo implicherebbe che la classe P coincide con la classe NP (in breve, si avrebbe P=NP).
Una scoperta del genere, oltre ad assicurare al suo scopritore il milione di dollari messo in palio dal Clay institute, renderebbe inutili tutti i sistemi di protezione dati e di cifratura esistenti.
Ora, è piuttosto chiaro che il sudoku nxn (cioè non solo 9×9, ma di grandezza generica) è un problema in NP, anche perchè i metodi di soluzione prevedono dei ‘tirare ad indovinare’ ogni tanto (vedi http://www.sudoku.org.uk/PDF/Solving_Sudoku.pdf). Ma in più, come ho detto all’inizio, il sudoku è stato dimostrato essere un problema NP-completo. Quindi: chi riuscisse a trovare una strategia veloce (cioè deterministica e polinomiale in n) per fare tutti i sudoku nxn vincerebbe un milione di dollari e manderebbe a catafascio mezzo sistema bancario mondiale.
(Anche se, per quest’ultimo scopo, basterebbe inventare un computer non-deterministico. Cosa che si sta cercando di fare, usando la logica quantistica – ma questo è un altro discorso).
Per concludere, uno stuzzichino: a quanto pare, l’ultima delle nostre domande (quanti numeri dati al minimo ci vogliono per determinare un sudoku) non ha ancora risposta. Ecco un esempio delle tante ‘domande aperte’ che ancora popolano la matematica!
Complexity classes P and NP su Wikipedia
il Sudoku su Wikipedia