I problemi classici dell’antichità e la risolubilità effettiva
(da E.Ambrisi, Problemi e teorie nell’insegnamento della matematica, La Scuola, n.183,1996)
[…] sempre si è parlato di risolubilità dei problemi tant’è che l’antichità ci ha tramandato alcuni classici problemi irrisolubili: la duplicazione del cubo, la trisezione di un angolo, la quadratura del cerchio. Non “classica”, ma non meno importante, è la irrisolubilità per radicali delle equazioni algebriche di grado maggiore di quattro.
In questa irrisolubilità, però, v’erano interessati gli strumenti utilizzabili.
Ad esempio, per la trisezione di un angolo: il compasso e la riga non graduata. I radicali, appunto, per le equazioni algebriche di grado maggiore o uguale al quinto.
Ma se un angolo non è trisecabile con un compasso ed una riga non graduata, possiamo sempre dire:
bene, usiamo il compasso e la riga graduata
e per un’equazione algebrica potremmo dire:
utilizziamo il metodo di Newton.
Quindi la risolubilità o meno di un problema deve essere vista in funzione di un metodo effettivo di calcolo. Dell’esistenza cioè di un qualsiasi algoritmo di risoluzione.
Il decimo problema di Hilbert ad esempio consiste nel fornire un metodo effettivo, ovvero un algoritmo, per stabilire se una qualsiasi equazione diofantea possiede o meno una soluzione (se cioè possiede o meno una soluzione fra tutti i numeri) .
La soluzione del problema è negativa: fu dimostrato che un tale metodo effettivo non esiste.
Il decimo problema di Hilbert fu risolto dal lavoro collettivo di Davis, Putnam e Robinson (1961) e Matijasevic (1970).
Ma oltre alla risolubilità effettiva esiste però un’altra questione che interessa ed ha rilevanza pratica notevole: il tempo. Un problema può essere risolubile in linea di principio ma la sua soluzione richiedere migliaia o milioni di anni per essere computata.
Un esempio immediato è l’ordinaria moltiplicazione di numeri interi positivi.
Un problema la cui risposta, mediante una macchina di Turing – schema più generale per un precedimento effettivo di calcolo – richieda venti miliardi di anni è, dunque, in linea di principio, risolubile, ma va considerato insolubile ai fini pratici.
E’ questa difficoltà o relativa impossibilità a costituire la chiave di sicurezza dei codici segreti per la protezione dell’informazione. Nessun codice è, in linea di principio, indecifrabile. Ma è un codice accettabile se, anche usando i calcolatori più veloci, la “spia” impiega miliardi di anni per decrittarli. I crittografi hanno sviluppato una collezione di operazioni di codificazione, dette funzioni trappola o unidirezionali , di semplice esecuzione nella direzione in cui il messaggio viene trasformato in codice, ma che, nella direzione contraria, richiederebbero miliardi di anni per essere portate a termine. Quando cioè sarebbe caduta, e da tempo, ogni ragione alla protezione dell’informazione.
Un esempio semplice di operazione di questo tipo, lenta in un verso e veloce nel verso opposto (da cui il nome di trappola) è quello di prendere due o più numeri primi abbastanza grandi, per esempio composti ognuno di cento o duecento cifre, e moltiplicarli tra loro.
Questa operazione di moltiplicazione è molto semplice per un calcolatore.
Ma se si mostra alla macchina il risultato e le si chiede di trovare quei numeri primi che sono i divisori esatti del numero dato, ebbene per trovarli impiegherà decisamente un lungo periodo di tempo, certo migliaia di anni. Ciò suggerisce che il problema della fattorizzazione è un problema NP (non deterministico in tempo polinomiale).
COMMENTS