P vs NP ed il problema del numero 42

P vs NP – Il problema X di Hilbert, incluso nella celebre lista dei 23 problemi matematici irrisolti presentata al 13° Congresso Internazionale di Matematica ad agosto 1900 a Parigi, riguarda la ricerca di un algoritmo che possa determinare, in un numero finito di passi, se un’equazione diofantea con n incognite ha soluzioni in numeri razionali interi. In altre parole:

 xⁿ + yⁿ + zⁿ + tⁿ + … = k    con n ≠ 2 – x, y, z, t, … razionali interi  e k = razionale intero

Un concorso da 7 milioni di dollari

Sino dai tempi di Pitagora, il problema di stabilire se per n ≠ 2 esistano soluzioni nel campo dei Razionali Interi ha affascinato e coinvolto centinaia di studiosi. Da Eulero a Dirichelet, Legendre, Lamé sino a Pierre de Fermat, ci hanno provato senza successo. Oggi il problema è spesso citato come Ultimo Teorema di Fermat. Tale problema venne posto nella forma specifica seguente:

x³ + y³ + z³ = k      con k = intero  0 < k < 100   (0.1)

dall’Università di Cambridge nel 1954, unitamene al Clay Mathematics Institure, che lo inserì in un concorso dotato di 7 milioni di dollari, per la soluzione dei 7 problemi matematici irrisolti.

P vs NP

Il problema della soluzione di equazioni diofantee nella forma specifica (0.1) venne risolto per diversi valori di k (33 ultima soluzione trovata) tranne per il numero 42, la cui soluzione venne individuata solo nel 2019 da Andrew Booker e pubblicata su Research in Number Theory. I valori di x, y, z sono:

 x = – 80.538.738.812.075.974; y = 80.435.758.145.817.515 e z = 12.602.123.297.335.631;

ed hanno richiesto l’impiego parallelo di alcune miglia di computer. Infatti, si immagini solo di calcolare il cubo di x = – 80.538.738.812.075.974, ottenendo un numero mostruoso di almeno 38 cifre (od oltre), altrettanto dicasi per y e z.

Questo, peraltro, nella ipotesi di aver già trovato i valori di x, y, e z e di voler verificare se tale soluzione è esatta. Al contrario, fissato il risultato (il numero 42) trovare i valori di x, y, z che soddisfino l’equazione x³ + y³ + z³ = 42 ha richiesto 67 anni e l’impiego di calcolo parallelo di miglia di PC.

Il problema di verificare la soluzione di un algoritmo è un problema di complessità P, cioè, un problema che una Macchina di Turing deterministica può risolvere in un tempo polinomiale rispetto al numero di dati disponibili; mentre è di complessità NP un problema la cui soluzione è calcolabile in un tempo polinomiale con una Macchina di Turing non deterministica. Sinteticamente, P prevede la verifica delle soluzioni (non il loro calcolo), mentre NP considera la individuazione delle soluzioni; il problema  diviene allora:

È più oneroso verificare la soluzione ad un problema o trovarne la soluzione?                      

Dove  per “oneroso” si intende computazionalmente.

P vs NP e il problema del numero 42

Un esempio assolutamente intuitivo al punto da potersi considerare banale è il problema dal Numero 42 ridotto a termini elementari ed analizzato per il numero 36:

x³ + y³ + z³ = k

Si cerca, quindi, la soluzione per k = 36. Viene utilizzato il metodo della “ forza bruta” ovvero della verifica per tentativi:

 x     y    z                                         

 1    1     1    = 1 + 1 + 1 =  3 < 36    se risultato < 36  z’ = z + 1;

 1    1     2    = 1 + 1 + 8 = 10 < 36    se risultato < 36  z” = z’ + 1;

 1    1     3    = 1 +1+27= 29 < 36    se risultato < 36  z”’ = z” + 1;

 1    1     4    = 1 + 1 + 64 = 66 > 36    se risultato > 36  ritornare al II passo e porre y’ = y + 1;

 1    2     2    = 1 + 8 + 8 = 17 < 36    se risultato < 36  z = z”’;

 1    2     3    = 1 + 8 + 27 = 36 = 36.

Nell’esempio specifico, la ricerca della soluzione NP comporta 18 elevazioni cubiche ed una somma (54 operazioni elementari), mentre la verifica P per x = 1; y = 2, z = 3 comporta 3 elevazioni cubiche ed una somma (10 operazioni elementari). Quindi possiamo dire che:

P < NP

Crittografia e P vs NP

Il problema P e NP riveste enorme importanza nella crittografia digitale che, fondamentalmente, si basa sulla fattorizzazione dell’elemento digitalizzato da fattorizzare (chiave, password, ecc.). Da qui ne deriva il problema della sicurezza informatica dei dati.

Un problema di tipo P

Data una fattorizzazione, ossia una sequenza di fattori primi ciascuno con il suo esponente, è facile trovare il numero di partenza: basta moltiplicare tra loro tutti i fattori. D’altra parte (problema di tipo NP) trovare tutti i fattori di numeri molto grandi è un’impresa complessa: attualmente non esiste un algoritmo efficiente che lo risolva. 

RSA – 768 è un numero digitale che espresso nel sistema decimale appare come:

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

Per la sua fattorizzazione ci sono voluti 2 anni e centinaia di computer in parallelo! La sicurezza informatica diviene di fatto, una questione di tempo (e di velocità di calcolo). Anche in banali applicazioni meccaniche (lucchetto digitale a 4 cifre) può risultare difficile separare P da NP.