Parliamo di Matematica. Che significa oggi risolvere un problema? E quando un problema è irrisolubile?
«L’antichità classica ci ha tramandato famosi problemi irrisolti quali la quadratura del cerchio, la duplicazione del cubo, la trisezione dell’angolo.Si tratta di una irrisolubilità particolare, dovuta alla limitazione imposta agli strumenti utilizzabili. Invece, oggi che significa risolvere un problema? E quando un problema è irrisolubile? Quali esempi sceglieresti per illustrare meglio la questione?»
Questo testo è uno dei temi che il Ministero della Pubblica Istruzione propose agli studenti delle scuole secondarie di secondo grado nell’anno scolastico 2007/08. Otto tracce pensate e messe a punto da un gruppo di ispettori tecnici, «sulla base di analoghe tracce già elaborate qualche anno prima, nell’ambito delle iniziative tese a migliorare l’apprendimento degli studenti in matematica» e inviate alle scuole con la convinzione che avrebbero potuto stimolare il gusto di parlare, leggere e scrivere di matematica.
L’iniziativa di allora, denominata “Parliamo di matematica”, sarebbe auspicabile ancora oggi: le sue finalità restano immutate e dunque attuali, così come i temi proposti. Ne è prova la domanda contenuta nella traccia: che cosa significa oggi risolvere un problema?
I problemi classici dell’antichità
Paolo Ruffini (1765-1822)
L’antichità ci ha lasciato tre celebri esempi di problemi impossibili da risolvere con la riga e il compasso:
La loro impossibilità fu dimostrata solo in epoca moderna: Pierre Wantzel (1837) per i primi due casi, Ferdinand Lindemann (1882) per il terzo. Similmente, nel campo dell’algebra, Ruffini, Abel e Galois mostrarono che le equazioni di grado superiore al quarto non sono in generale risolubili per radicali.
La risolubilità di questi problemi classici è dunque legata agli strumenti utilizzati. Tuttavia:
Se non è possibile trisecare un angolo con riga e compasso, basta ammettere la riga graduata per ottenere una costruzione valida.
Se non si sa risolvere per radicali un’equazione di quinto grado, si può utilizzare un algoritmo iterativo come il metodo di Newton, ottenendo soluzioni con l’approssimazione desiderata.
Questo sposta la prospettiva e mostra come il concetto di risolubilità vada interpretato in funzione dell’esistenza di un metodo effettivo di calcolo, ovvero di un algoritmo.
Hilbert, Gödel e i limiti della risolubilità
Nel 1900 David Hilbert presentò la lista dei 23 problemi che al momento risultavano irrisolti. Fu un avvenimento di grande portata che scosse la comunità matematica indirizzandola alla ricerca delle soluzioni di quei grandi problemi.
In particolare, il decimo chiedeva un algoritmo capace di stabilire se un’equazione diofantea ammette soluzioni intere.Ma che cos’è un’equazione diofantea? È un’equazione polinomiale con coefficienti interi, come ad esempio:
[ x^2 + y^2 = z^2 ]
che ammette soluzioni intere ben note: (x=3, y=4, z=5).
La sfida posta da Hilbert era però più generale: esiste un metodo effettivo che, data qualsiasi equazione diofantea, decida se ammette soluzioni intere?La risposta arrivò qualche decennio dopo ed è negativa: tra il 1961 e il 1970 Davis, Putnam, Robinson e Matijasevič dimostrarono che un tale algoritmo non esiste. È uno dei passaggi più importanti nella storia della logica e dell’informatica teorica, perché sancisce un limite alla risolubilità.
Ma i limiti alla speranza hilbertiana erano stati preannunciati già da Kurt Gödel nel 1931. Con i suoi celebri teoremi di incompletezza mostrò che in ogni sistema formale sufficientemente potente da contenere l’aritmetica esistono enunciati veri che non possono essere dimostrati all’interno del sistema stesso.Ne consegue che non esiste un algoritmo capace di decidere la verità o falsità di tutti gli enunciati aritmetici: la matematica non è una costruzione perfettamente completa e coerente, ma porta in sé i segni dell’incompletezza e dell’indecidibilità.
Il significato di questo risultato è molto generale. Ad esempio: per quanto si costruisca un computer potente o si immagini una macchina di calcolo perfetta, esisterà sempre almeno un problema che quel calcolatore non sarà in grado di risolvere. È un limite intrinseco, non tecnologico, che segna il confine tra ciò che è calcolabile e ciò che resta indecidibile.
Ma questo limite porta con sé anche un messaggio positivo: la matematica non si esaurirà mai. Non potremo mai dire di aver dimostrato l’ultimo teorema, perché ci sarà sempre un nuovo problema, una nuova sfida.Lo aveva intuito già Platone, quando descriveva la matematica come ciò che “sempre è e che non nasce e non perisce”: un sapere che non ha un inizio ed è senza fine, che accompagna l’umanità nel suo cammino.
Dal possibile in principio al possibile in pratica
C’è però una seconda questione cruciale che riguarda la risolubilità di un problema: il tempo! Un problema può essere risolvibile in teoria, ma se la sua soluzione richiede miliardi di anni di elaborazione, diventa impraticabile.
Si pensi a problemi che crescono rapidamente in complessità con l’aumentare della dimensione, come il calcolo del percorso ottimale in una rete o la risoluzione generale di un sudoku molto grande. Qui entra in gioco la distinzione tra classi di complessità, come P e NP.
Un problema si dice risolubile in tempo polinomiale (classe P) se esiste un algoritmo che lo risolve in un tempo che cresce relativamente lentamente al crescere della dimensione del problema, ad esempio proporzionale a ( n^2 ) o ( n^3 ). In questi casi, anche problemi molto grandi restano affrontabili con computer sufficientemente potenti.
Se invece il tempo cresce in modo esponenziale (ad esempio come ( 2^n )), la risoluzione diventa impraticabile già per valori moderati di ( n ). I problemi della classe NP sono quelli per cui, pur non conoscendo un algoritmo polinomiale, una soluzione proposta può essere verificata velocemente.
La crittografia come applicazione moderna
Il tema della risolubilità effettiva non è solo una questione teorica, ma ha conseguenze pratiche enormi, ad esempio nella crittografia, cioè l’arte di proteggere i messaggi rendendoli leggibili solo a chi possiede la chiave segreta.
La sicurezza dei sistemi crittografici moderni si basa proprio su una asimmetria: ci sono operazioni facili in un verso ma difficilissime nell’altro. Queste operazioni prendono il nome di funzioni trappola o unidirezionali.
Un esempio semplice è la moltiplicazione di due grandi numeri primi: è un’operazione immediata anche per un computer. Ma fare il processo inverso — cioè risalire ai fattori primi a partire dal loro prodotto — è invece un compito che, con i metodi classici, richiederebbe tempi astronomici.
Su questa idea si fonda l’algoritmo RSA (1977), ancora oggi usato per proteggere transazioni bancarie, carte di credito e comunicazioni online. RSA non è indecifrabile in senso assoluto, ma è considerato sicuro perché anche i computer più potenti impiegherebbero miliardi di anni per violarlo con i metodi tradizionali.
Con l’avvento del calcolo quantistico, lo scenario è cambiato.L’algoritmo di Shor (1994) ha dimostrato che un computer quantistico sufficientemente potente sarebbe in grado di fattorizzare grandi numeri in tempi brevi, compromettendo la sicurezza dei sistemi basati su RSA.
Per questo oggi si parla di crittografia post-quantistica: nuovi metodi di cifratura studiati per restare sicuri anche nell’era dei computer quantistici.Questi sistemi non si basano più solo sulla difficoltà della fattorizzazione, ma su altri problemi matematici ritenuti resistenti agli attacchi quantistici, come quelli legati alle reti geometriche (lattice).
Il problema del commesso viaggiatore (TSP)
Immaginiamo un commesso viaggiatore che debba visitare una serie di città e poi tornare al punto di partenza: qual è il percorso più breve che collega tutte le città una sola volta?La domanda sembra semplice, ma la difficoltà cresce vertiginosamente:
con 4 città ci sono solo 3 percorsi possibili,
con 10 città i percorsi diventano più di 180.000,
con 20 città il numero supera già quello delle stelle nella nostra galassia.
Il TSP è un tipico esempio di problema NP-difficile: conosciamo algoritmi che provano tutte le soluzioni (tempo esponenziale), ma non ne abbiamo di efficienti in tempo polinomiale.Per questo in pratica si usano algoritmi approssimati, capaci di dare percorsi “quasi ottimali” in tempi rapidi.Le applicazioni sono numerosissime: dalla logistica (consegne su strada) alla pianificazione di voli e trasporti, fino al sequenziamento del DNA.
Il problema della rete minima (Steiner tree problem)
Generalizza il teorema di Viviani: dato un triangolo A, B, C, trovare il punto P che minimizza ( PA + PB + PC ) (soluzione: il punto di Fermat–Torricelli).Con più punti, si chiede la rete di connessioni di lunghezza minima.È il problema di Steiner, risolvibile ma NP-difficile: la complessità cresce così rapidamente che la soluzione esatta diventa impraticabile già con poche decine di punti.Per questo si usano algoritmi approssimati ed euristici, che forniscono reti quasi ottimali.Applicazioni tipiche: reti elettriche, telefoniche, informatiche e logistiche.
Il protein folding
Determinare la forma tridimensionale di una proteina a partire dalla sequenza degli amminoacidi è teoricamente risolvibile, ma di enorme complessità computazionale. Negli ultimi anni l’intelligenza artificiale ha compiuto passi decisivi: AlphaFold 2 (DeepMind, 2020), vincendo la competizione internazionale CASP14, ha mostrato come modelli di apprendimento automatico possano fornire soluzioni con un’accuratezza vicina a quella sperimentale, con grande impatto su biologia e medicina.
La congettura di Collatz
Accanto ai grandi problemi della scienza e dell’informatica, esistono enigmi semplicissimi da enunciare che resistono da decenni: uno dei più celebri è la congettura di Collatz.
È forse l’esempio più sorprendente di come un problema possa essere semplice da spiegare ma difficilissimo da risolvere.Le regole sono elementari:
se un numero è pari, lo si divide per 2;
se è dispari, lo si moltiplica per 3 e si aggiunge 1.
Partendo da un numero qualsiasi e applicando queste regole passo dopo passo, la sequenza dei valori sembra sempre scendere fino a raggiungere 1. Le orbite descritte hanno tutte per attrattore 1.Ad esempio, partendo da 7 si ottiene: 7 → 22 → 11 → 34 → 17 → 52 → … → 1.
La domanda è: accade sempre così, qualunque sia il numero di partenza?Tutti gli esperimenti numerici lo confermano, anche con numeri enormi, ma una dimostrazione generale ancora non esiste.
Per questo la congettura di Collatz è diventata un simbolo: ci ricorda che in matematica “semplice da enunciare” non significa necessariamente “facile da risolvere”.Un problema che si può proporre già ai ragazzi delle prime classi della scuola secondaria di secondo grado, ma che resta un enigma aperto anche per i matematici di oggi.
Conclusione
Un problema “impossibile” con riga e compasso può diventare risolvibile con strumenti diversi; un problema che richiede miliardi di anni per essere risolto non ha senso pratico, anche se in teoria è affrontabile. Il ricorso a metodi effettivi rappresenta comunque la strada maestra della risolubilità. Ma quali sono questi mezzi effettivi? È qui che entra in gioco la moderna teoria della computabilità, che non è nè più e nè meno che la teoria della ricorsività, secondo la tesi di Church–Turing.
Riflettere su queste questioni — dai Greci e le loro costruzioni con riga e compasso, a Hilbert e Gödel, dalle impossibilità teoriche alle difficoltà pratiche di calcolo — significa portarsi al cuore stesso della natura della matematica. Del resto, che cos’è “fare matematica” se non l’attività di risolvere problemi? Vuol dire essere portati a mettere in luce le relazioni tra incompletezza e indecidibilità, tra computabilità effettiva e metodi ricorsivi poter dare una risposta alla domanda del tema: “che cosa significa oggi risolvere un problema?”. E vuol dire, infine, trovare spazio per “parlare di matematica” e stimolare studenti e docenti a discuterne, leggerne e scriverne. Perché parlare di matematica è già un modo per viverla e comprenderla meglio.
