211service.com
Cosa significa 'P vs. NP' per il resto di noi?
I programmatori e gli scienziati informatici hanno ronzato per la scorsa settimana sull'ultimo tentativo di risolvere una delle domande più fastidiose dell'informatica: il cosiddetto problema P versus NP.
Vinay Deolalikar, ricercatore presso HP Labs a Palo Alto, in California, ha pubblicato la sua prova online e l'ha inviata a diversi esperti del settore il 6 agosto. I colleghi hanno immediatamente iniziato a sezionare la prova su blog accademici e wiki. Le prime reazioni sono state rispettose ma scettiche e l'attuale consenso è che l'approccio di Deolalikar è fondamentalmente imperfetto.
Una solida prova guadagnerebbe fama e fortuna a Deolalikar. Il Istituto di matematica dell'argilla a Cambridge, MA, ha nominato P contro NP come uno dei suoi problemi del Millennio e offre $ 1 milione a chiunque fornisca una prova verificata.
Ma P contro NP è più di un semplice puzzle matematico astratto. Cerca di determinare, una volta per tutte, quali tipi di problemi possono essere risolti dai computer e quali no. I problemi di classe P sono facili da risolvere per i computer; cioè, le soluzioni a questi problemi possono essere calcolate in un tempo ragionevole rispetto alla complessità del problema. Nel frattempo, per i problemi NP, una soluzione potrebbe essere molto difficile da trovare, forse richiedendo miliardi di anni di calcoli, ma una volta trovata, è facilmente verificabile. (Immagina un puzzle: trovare la giusta disposizione dei pezzi è difficile, ma puoi capire quando il puzzle è finito correttamente solo guardandolo.)
I problemi di classe NP includono molti problemi di abbinamento e ottimizzazione di pattern di grande interesse pratico, come la determinazione della disposizione ottimale dei transistor su un chip di silicio, lo sviluppo di modelli di previsione finanziaria accurati o l'analisi del comportamento di ripiegamento delle proteine in una cellula.
Il problema P contro NP si chiede se queste due classi siano effettivamente identiche; cioè, se ogni problema NP è anche un problema P. Se P è uguale a NP, ogni problema NP conterrebbe una scorciatoia nascosta, che consente ai computer di trovare rapidamente soluzioni perfette. Ma se P non è uguale a NP, allora non esistono scorciatoie del genere e i poteri di risoluzione dei problemi dei computer rimarranno fondamentalmente e permanentemente limitati. L'esperienza pratica suggerisce in modo schiacciante che P non è uguale a NP. Ma fino a quando qualcuno non fornisce una valida dimostrazione matematica, la validità dell'assunto rimane in discussione.
Anche se la prova di Deolalikar si rivelasse valida, la domanda rimane: che impatto avrebbe una tale prova su aree rilevanti dell'informatica?
Superficialmente, si potrebbe pensare che la risposta non sia molto. Dimostrare che P non è uguale a NP confermerebbe solo ciò che quasi tutti già presumono essere vero per scopi pratici, spiega Scott Aaronson , ricercatore della complessità presso il Computer Science and Artificial Intelligence Laboratory del MIT.
Ad esempio, la nostra incapacità di fattorizzare in modo efficiente enormi numeri compositi (un classico problema NP) costituisce la base della moderna crittografia, che è alla base di tutto, dalla sicurezza nazionale agli acquisti su Amazon.com. Non abbiamo bisogno di una prova formale che P non sia uguale a NP per fare affidamento sulla congettura, dice Aaronson. I programmatori conoscono il problema e sarebbero entusiasti di vedere che P non è uguale a NP dimostrato, ma a livello quotidiano sanno che riformulare [un problema NP] in qualcosa di più semplice ha molto più senso che cercare di risolvere il problema matematico problema del secolo.
Poiché i problemi di classe NP sono così pervasivi (anche i sudoku e le ricerche sugli orari delle compagnie aeree su Bing.com sono computazionalmente difficili), vengono costantemente scoperte soluzioni alternative innovative. L'ottimizzazione stocastica, ad esempio, imita la casualità che si trova nei sistemi fisici (come il raffreddamento dei metalli o la mutazione del DNA) al fine di produrre soluzioni sufficientemente buone invece di soluzioni computazionalmente difficili.
I tentativi di far fronte all'assunto che P non è uguale a NP ci aiutano a sviluppare nuove tecnologie mentali, afferma Richard Lipton , un informatico della Georgia Tech che studia il problema P contro NP. Anche se scriviamo algoritmi da decenni, non capiamo appieno di cosa siano capaci, continua. Quindi, anche se dimostrassi che P non è uguale a NP, cosa in cui tutti credono già, dovrebbe espandere radicalmente la nostra comprensione di queste capacità e rendere possibili molte cose nuove con i computer, oltre a tutte le soluzioni intelligenti che abbiamo già fondare.
Quindi, se il progresso incrementale può ancora generare innovazione utile, perché i titani della ricerca industriale come Google, Microsoft e HP (che si sono rifiutati di commentare per questo articolo) dedicare enormi team di ricercatori al puzzle P non equivale a NP? Dimostrare un aspetto negativo è semplicemente incredibilmente difficile e, dal punto di vista [di una grande azienda], probabilmente non ha un grande impatto sul prossimo trimestre finanziario o anche sui prossimi anni della loro attività, afferma Lipton. È più un problema a lungo termine.
Certo, c'è sempre l'alternativa: provare che P fa infatti uguale NP. Ma non trattenere il respiro, dice Aaronson. Ci sono buone ragioni per cui pochissime persone credono che P sia uguale a NP, dice. Se così fosse, vivremmo in un universo fondamentalmente diverso e probabilmente lo avremmo notato ormai.