backup del Post

P != NP (o no?)

Oggi la comunità matematica mondiale è stata scossa da una notizia bomba: un ricercatore dell’HP, Vinoy Deolalikar, ha affermato di avere dimostrato che effettivamente P != NP. Su Good Math, Bad Math, MarkCC fa un rapido resoconto del problema per i matematici non esperti in teoria della complessità. E per chi matematico non è?

Per capire cosa significhi la sigla del titolo, che assomiglia tanto a una crittografia, bisogna fare alcuni passi indietro. Come penso sappiate dalle barzellette sulla categoria, il matematico è solo interessato a scoprire se la soluzione al problema esiste; al più cerca di dimostrare che è unica. Possiamo avere alcune categorie particolari di matematici; i logici vorranno magari essere certi che il problema sia decidibile, mentre i costruttivisti vogliono essere certi che la soluzione sia computabile, cioè esista un algoritmo che prima o poi termini. Ma qui ci si ferma: che ci vogliano dieci, mille, un milione di o anche un numero di Skewes di operazioni è irrilevante. Ma per gli informatici, che i conti li fanno davvero (beh, li fanno fare ai computer, ma il concetto è quello) la cosa è ben diversa.

A dirla tutta, nemmeno gli informatici sono poi così interessati al numero esatto di operazioni, e preferiscono avere una stima sufficientemente generica che indichi come il numero di operazioni cresca al crescere dei dati di partenza; è ovvio che ordinare mille elementi è più lungo che ordinarne dieci, ma quanto è più lungo? Per definire il “quanto” si usa il concetto di ordine di grandezza, o più precisamente la “notazione O grande”. Data una dimensione di dati di input n, si dice che (la complessità di) un algoritmo è O(f(n)) se il numero di operazioni necessarie per eseguirlo è un multiplo di f(n) più altra roba che all’infinito “conta di meno”. Se per esempio un algoritmo richiedesse 5n³+1000000n²+10²⁰ operazioni, si dice che è O(n³), anche se per n=1000 il termine che conta è quello costante. Ah: se si parla di algoritmi numerici, storicamente si considera il numero di moltiplicazioni necessarie, e non ci si preoccupa delle addizioni che nei primi computer erano molto più semplici da eseguire delle moltiplicazioni. Ma queste sono minuzie. Per fare un esempio pratico, i migliori algoritmi per ordinare n elementi richiedono O(n log n) operazioni, e si è anche dimostrato che quello è il limite teorico; si potrà diminuire il numero effettivo di operazioni, ma saranno sempre grosso modo quelle lì.

Possiamo finalmente arrivare alla nostra notazione iniziale. I problemi per cui è noto un algoritmo per risolverli che richiede un numero polinomiale di operazioni fanno parte della classe P, che sta appunto per “polynomial”. Esempi di questi algoritmi sono l’ordinamento di n numeri, oppure il prodotto di due matrici n*n, il cui algoritmo record attuale richiede O(n^2.376) operazioni. Ci sono poi alcuni problemi teorici che si sa essere intrinsecamente difficili e richiedere un numero di operazioni che cresce esponenzialmente con n; questi fanno parte della classe EXP. Visto che eⁿ cresce più in fretta di n^k per qualunque k, problemi di questo tipo sono intrinsecamente tosti, ma come ho detto non capitano in pratica. C’è poi un’altra categoria di problemi, chiamati appunto NP; la sigla non sta per “non polynomial”, come si potrebbe pensare, ma per non deterministic polynomial.

Che significa? Fino a ieri, significava che non sono noti algoritmi di complessità polinomiale per risolverli, ma che sarebbe possibile risolverli in tempo polinomiale se avessimo un computer non deterministico. Il modo più semplice per capire questa definizione è immaginare l’Algoritmo di Gastone. Gastone Paperone, essendo per definizione fortunatissimo, ogni volta che deve fare una scelta trova sempre quella giusta; in questo modo evita tutti i passi falsi e arriva alla soluzione di un problema NP in tempo polinomiale, mentre non solo Paolino Paperino che è notoriamente uno sfigato ma anche Qui, Quo, Qua con il loro Manuale delle Giovani Marmotte ci metteranno un tempo esponenziale. Un modo alternativo per definire i problemi NP è dire che sono quelli per cui verificare la soluzione (se si pone il problema in modo tale che si può dare una risposta sì/no) richiede tempo polinomiale. Per fare un esempio, immaginate di avere un insieme di numeri interi, positivi e negativi, e che vi si chieda se c’è un sottoinsieme la cui somma sia esattamente zero. Per risolvere il problema occorre provare tutti i gruppi di 2, 3, 4, … n numeri, e quindi il costo computazionale è esponenziale, dell’ordine di 2ⁿ; ma se il vostro nonno vi dice in sogno di provare un ben preciso insieme di numeri, potete vedere in fretta se sono effettivamente una soluzione.

Da decenni gli informatici cercano di capire se le due classi sono identiche, e noi semplicemente non siamo in grado di trovare gli algoritmi buoni per risolvere i problemi NP in tempo polinomiale, o se sono diverse e quindi quei problemi sono davvero difficili. Si è scoperta un’intera classe di problemi, detti NP-completi e che si trovano spesso nella vita reale, per cui “risolto uno, risolti tutti”, nel senso che c’è un algoritmo polinomiale che data la soluzione a uno di questi problemi ne ricava una per ciascuno degli altri; ma questo non basta. Se ora effettivamente Delolalikar ha dimostrato che P != NP dobbiamo metterci il cuore in pace; anche quei problemi sono intrinsecamente difficili. Non che la dimostrazione sia facile, visto che sembra assembli risultati da branche diversissime della matematica: una dimostrazione insomma non bella, ma utile; utile anche per guadagnare un milione di dollari, visto che questo è uno dei Millennium Problems.

Ma poi sarebbe davvero utile? Beh, non proprio. Nella vita reale ci sono algoritmi per la soluzione di problemi NP-completi che danno quasi certamente la soluzione in tempo polinomiale, oppure che terminano quasi sempre in tempo polinomiale; insomma, all’atto pratico le soluzioni ce le troviamo comunque. Anche il problema attualmente più importante per tutta la crittografia, quello della fattorizzazione di un numero, potrebbe prima o poi avere una soluzione di questo tipo, anche se personalmente ne dubito. Resta il punto che anche gli esperti di teoria della complessità sono matematici; come dicevo all’inizio, a loro importa vedere il teorema dimostrato, anche se poi non lo useranno in pratica.