La fattorizzazione non è un problema NP-completo (che si sappia)

Questa storia della dimostrazione (ormai quasi definitivamente smontata) che P≠NP sta riportando in superficie il diffusissimo errore secondo cui se P≠NP allora i crittografi e i loro clienti potranno dormire sonni tranquilli (ho citato la mia amica Sylvie, ma è un'affermazione piuttosto frequente).

L'errore consiste nel considerare il problema della fattorizzazione dei numeri composti un problema NP-completo, cosa che non è affatto dimostrata e, anzi, ci sono forti indicazioni che portano a credere che non sia tale: se avete tempo, vi ri-consiglio caldamente tutte le lezioni del corso di Scott Aaronson: Quantum Computing Since Democritus; se avete fretta e vi interessa la questione della "difficoltà" della fattorizzazione, potete limitarvi alla lezione n° 6: P, NP, and Friends.

Che quello della fattorizzazione sia un problema NP-completo è un fraintendimento molto diffuso, io lo scoprii proprio quando mi imbattei nelle lectures di Scott Aaronson: in realtà molto probabilmente si tratta di un problema "più semplice" dei problemi NP-completi, per cui potrebbe benissimo darsi che si scopra che sia un problema "facile" (P) senza che ciò implichi che siano facili anche i problemi NP-completi (molto più probabilmente si tratta di un problema che ricade in un classe intermedia fra P e NP). Detto al contrario: anche se fossimo in grado di dimostrare che i problemi NP-completi sono "davvero" difficili, il problema della fattorizzazione dei numeri composti (e dunque il problema di violare un codice crittografico) potrebbe benissimo rientrare nella categoria dei problemi "facili" (P).

Tant'è che per il problema della fattorizzazione esiste un algoritmo quantistico (il famoso algoritmo di Shor) capace di risolverlo in tempo polinomiale, mentre — nonostante si senta spesso dire il contrario — non è noto alcun algoritmo quantistico capace di risolvere problemi NP-completi in tempo polinomiale, e se mai un giorno si dovesse scoprirne uno, sarebbe sicuramente molto diverso dall'algoritmo di Shor.

Vi siete persi?

Spero di riuscire a buttar giù un "riassuntino" della faccenda quanto prima (cioè: ho già cominciato a scrivere qualcosa, ma sta venendo più lungo di quel che credessi; così ho pensato di uscire subito con questo post giusto per (tentare di) restare "sulla notizia"...).

 

Prima di chiudere, però, vorrei dire due parole sul perché questa questione dell'equivalenza (o meno) delle classi P e NP mi appassiona tanto.

Il fatto è che non si tratta di uno dei problemi da un milione di dollari, o di uno dei più difficili problemi matematici ancora irrisolti, ma si tratta del Problema tout court: se tutti i problemi NP fossero risolvibili polinomialmente, sarebbe possibile programmare un computer per risolvere in poco tempo anche tutti gli altri problemi da un milione di dollari.

C'è addirittura chi crede che l'impossibilità algoritmica di risolvere problemi NP-completi in tempo polinomiale sia consustanziale alla stessa struttura fisica di cui è fatto il mondo.

Come chi?, ma Scott Aaronson, no? :-)