Vinay Deolalikar degli HP Research Labs, un matematico delle reti, ha appena pubblicato in versione preliminare la prova che P ≠ NP. La questione è complessa, d’altronde riguarda la complessità. In parole povere, esistono domande alle quali un computer, una macchina deterministica, risponde sì o no in un tempo polinomiale e quelle domande rientrano nei problemi detti P, per polinomiali. Una sottoclasse riguarda invece problemi che, pur essendo P, richiedono una macchina non deterministica e sono quindi detti NP.
Ma è vero, matematicamente parlando, che non sono uguali? In questi giorni numerosi matematici stanno cercando di rispondere con un sì o un no. Se sì, Vinay Deolalikar vince il milione di dollari del premio Clay per aver risolto un problema del millennio. E i crittografi e i loro clienti potranno dormire sonni tranquilli. Se la risposta è no e qualcuno dimostra addrittura che P = NP, la crittografia sarebbe da rifare, i nostri dati non sarebbero più protetti. Con un po’ di talento e di fortuna un malintenzionato riuscirebbe a calcolare la combinazione unica di cifre dietro la quale si nascondono.
Però questo vorrebbe anche dire che i problemi NP potrebbero avere una soluzione generale e generatrice di nuovi algoritmi. Sarebbe fantastico. Tantissime ricerche in cui bisogna identificare la combinazione giusta tra migliaia o milioni di possibilità – basti pensare alla biologia: segnali, geni pleiotropici, i-Rna, proteine, vaccini, farmaci… – diventerebbero più veloci perché i computer ci arriverebbero da soli.
La prova è al vaglio della comunità e forse non lo supera. Aggiornamenti sui lavori in corso da Richard Lipton con la partecipazione di supercompetenti, anche di Terry Tao, medaglia Fields e un po’ scettico ma felice della discussione collettiva, e una voce wiki che aggrega le risorse. . Un’ultima nota, Vinay Doelalikar dedica il lavoro ai suoi, in particolare ai nonni
che hanno fatto di tutto per educare mio padre, malgrado l’estrema povertà. Questo lavoro fa parte del mio Matru-Pitru Rin (nota 1). Nota 1. Il debito verso la madre e il padre che un indù pio ritiene un obbligo ripagare in questa vita.
