La prova del sì e no

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.

1 Comment on La prova del sì e no

  1. A differenza di Deolalikar penso che P = NP. Poiché ne sono convinto ho provato a dimostrarlo, trovate tutto su: http://www.visainformatica.it/3sat.
    Sono solo 13 pagine e non richiedono conoscenze di matematica, ma solo di logica elementare. Chiunque può quindi confutare velocemente la mia presenta prova.
    Sono grato a chi vorrà inviarmi commenti, critiche o suggerimenti.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

Unisciti agli altri 1.132 follower

%d blogger cliccano Mi Piace per questo: