Showing posts with label PHYS771. Show all posts
Showing posts with label PHYS771. Show all posts

17 August 2010

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? :-)

15 April 2009

darwinisti teorici e darwinisti sperimentali

Il punto c di questo commento di sagredo su Progetto Galileo mi ha fatto ricordare che avevo un post nel cassetto. Finisco ora di scriverlo e lo pubblico subito.
 
C'era una volta (ennesima dimostrazione della tempestività con cui questo blog scatta sulla notizia) Scott Aaronson che annunciò la pubblicazione dell'ultima lezione del corso Quantum Computing Since Democritus. Ho avuto modo di parlare molto di questo corso, anche se meno di quel che mi sarebbe piaciuto. Avrei in tasca, per esempio, almeno un altro spunto che, periodicamente, prende a frullarmi per la testa, ma ormai sta cominciando a formarsi la muffa su quel Bonus Addendum nascosto in fondo alla terza lezione... chissà quando troverò il tempo di tornarci su (anzi, sto cominciando anche a scordarmi tutte le cose che volevo dire a riguardo...).
Nel frattempo, mi limito a sengalarvi quest'ultima lezione, anche perchè non si parla solo di complessità computazionale. Come sempre, del resto, nelle sue lezioni. Ma in questa in particolare, visto che si intitola Ask Me Anything. Anzi, mi permetto addirittura di riportarne, traducendoli molto liberamente (e rozzamente) in italiano, alcuni stralci più significativi e meno tecnici.

   —   ∴   —   

Scott: Altre domande? Magari una meno tecnica?
D: Come risponderesti ad un sostenitore dell'Intelligent Design? Senza farti sparare?
Scott: Be', davvero non saprei. E' uno di quei casi in cui potremmo applicare il principio antropico: se su questa cosa fosse stato possibile convincerlo con l'evidenza, non si sarebbe già convinto? Secondo me dobbiamo accettare che ci sono persone per cui la cosa più importante nelle proprie convinzioni non è se queste corrispondono al vero; altre proprietà sono più importanti, quali ad esempio il proprio ruolo in una comunità. Stanno giocando, cioè, un gioco diverso, in cui le credenze sono giudicate con standard diversi. E' come un giocatore di basket su un campo di calcio. Come potrà mai vincere?
[...]
Scott: E' chiaro che la religione svolge una qualche funzione, per le persone, altrimenti non sarebbe stata così onnipresente per migliaia di anni o non avrebbe resistito a significativi sforzi per eliminarla. Per esempio, forse le persone che credono che Dio stia dalla loro parte sono più coraggiose in battaglia. O forse la religione è uno dei fattori (fra altri più ovvi) che induce uomini e donne a sposarsi ed avere un sacco di bambini, e dunque rappresenta un tratto adattivo da un punto di vista darwiniano. Anni fa rimasi colpito da un fatto ironico: nell'America contemporanea abbiamo questo stereotipo di elite che crede nel darwinismo e vive spesso da solitario trentenne o quarantenne, e poi abbiamo lo stereotipo di quelli che rifiutano il darwinismo ma si sposano giovani e hanno 7 figli, 49 nipoti e 343 bisnipoti. A questo punto non è una gara fra darwinisti e anti-darwinisti; è una gara fra darwinisti teorici e darwinisti sperimentali!
Se quest'idea è corretta anche solo in parte — che le religioni sopravvivono perchè aiutano le persone a vincere le guerre, ad avere più bambini, etc — allora la domanda che si pone è: come sarai mai in grado anche solo di affrontarli se non diventando anche tu una religione alternativa?
D: Oh, sì, sono sicuro che questo è proprio quel che la gente pensa quando deve decidere se credere o meno in una religione.
Scott: Non sto dicendo che è qualcosa di consapevole, o che le persone la pensano proprio in questi termini. Certamente qualcuno lo fa, ma il punto è che non devono farlo, perchè il loro comportamento sia comunque descrivibile in questi termini.
D: Possiamo anche avere molti bambini senza accettare una religione, se vogliamo.
Scott: Certo, possiamo, ma lo facciamo, in media? Non ho numeri a portata di mano, ma credo che esistano studi che supportano il fatto che le persone religiose hanno in media più figli.
Ora, c'è un altro fattore chiave, ed è che alcune volte l'irrazionalità può essere la scelta più razionale, perchè è l'unico modo di dimostrare a qualcun altro che sei convinto di qualcosa. Tipo, se qualcuno si presenta alla tua porta chiedendoti cento dollari, è molto più probabile che tu glieli dia se ha gli occhi iniettati di sangue e un'aria davvero irrazionale — non hai idea di cosa starà per fare! L'unico modo di rendere efficace una strategia simile è fare in modo che l'apparenza di irrazionalità sia convincente. Il tizio non potrebbe semplicemente fingere, altrimenti lo capiresti. Deve essere molto, molto irrazionale e mostrarsi capace di vendicarsi di te a qualsiasi costo. Se credi che il tizio difenderà il suo onore fino alla morte, probabilmente non vorrai avere a che fare con lui.
Quindi la teoria è che la religione è un modo per convincere se stessi. Uno può dire di credere in un certo codice morale, ma gli altri possono capire che sta mentendo e non fidarsi di lui. D'altra parte, se uno ha una barba molto lunga e prega tutti i giorni e sembra davvero credere che l'aspetterà un inferno eterno se infrangerà i suoi precetti, sta costruendo il suo stesso convincimento. Secondo questa teoria la religione funzionerebbe come un modo di pubblicizzare una convinzione su un certo insieme di regole. Naturalmente le regole possono essere buone o possono essere terribili. Nondimeno, questa specie di convincimento pubblico ad obbedire a un insieme di regole, condite con ricompense e punizioni sovrannaturali, sembra essere un elemento importante di come le società si sono organizzate per migliaia di anni. E' il motivo con cui i potenti hanno convinto i propri sudditi a non ribellarsi, gli uomini hanno convinto le proprie mogli ad essere fedeli e le mogli convinto i propri mariti a non abbandonarle, eccetera.
Insomma, mi sembra che questi siano i tipi di forze "di teoria dei giochi" che Dawkins e Hitchens e gli altri crociati anti-religioni devono affrontare e che forse non riconoscono sufficientemente nei loro scritti. Ciò che gli rende le cose facili, naturalmente, è che i loro oppositori non possono semplicemente saltar fuori e dire "sì, naturalmente sono tutte sciocchezze, ma servono per queste importanti funzioni sociali!" Invece i difensori delle religioni spesso ricorrono ad argomenti che si demoliscono facilmente (almeno dopo Hume e Darwin) perchè la loro vera condizione, sebbene considerevolmente più forte, è di quelle che è molto difficile da sostenere apertamente!
Riassumendo, magari è vero che gli uomini (se sopravviveremo abbastanza a lungo) potrebbero arrivare a ripudiare le religioni, ora che abbiamo qualcosa di meglio con cui sostituire il loro potere esplicativo. Ma prima che ciò accada, credo che avremo bisogno almeno di capire meglio le funzioni sociali che la religione ha giocato per la maggior parte della storia e ancora gioca nella maggior parte del mondo, e forse avremo bisogno di trovare meccanismi sociali alternativi per risolvere lo stesso tipo di problemi.
D: Stavo pensando se ci fosse un altro caso in cui l'irrazionalità sia preferibile alla razionalità.
Scott: Da dove iniziare?
D: Specialmente se hai un'informazione incompleta. Come se avessi un politico che è ben convinto e che non cambierebbe mai i suoi ideali: saresti molto più sicuro che farà quel che dice di voler fare.
Scott: Perchè ha convinzioni. Crede in quel che dice. Per la maggior parte dei votanti, questo conta molto più che l'effettivo contenuto delle convinzioni. Bush da un'impressione molto buona di convinzione.
D: Ma non sono sicuro che ciò sia il meglio per gli interessi degli Stati Uniti.
Scott: Esatto, questo è il punto! Come combatti persone che sono diventati maestri nel meccanismo dell'irrazionalità razionale? Dicendo "no, guarda qui, i tuoi fatti si sono rivelati sbagliati"? A che gioco stai giocando? Prendi un altro esempio: un single al bar. Quelli che hanno più successo sono quelli più abili a convincere se stessi (almeno temporaneamente) di certe falsità: "Sono il più figo qui". Questo è un chiaro caso in cui l'irrazionalità sembra razionale, in un certo senso.

30 June 2008

Quantum Computing Since Democritus

Prosegue la pubblicazione delle lectures del corso di Aaronson del 2006. Dopo lo sprazzo isolato di febbraio, in questo giugno ben tre post hanno annunciato tre nuove puntate del corso.
Ovviamente non ho ancora trovato il tempo di leggerle tutte, ma già la prima, How Big Are Quantum States?, offre spunti molto interessanti. Aaronson, lo sappiamo, ama le frasi ad effetto, ed anche ora parte alto:
"computer science" is a bit of a misnomer; maybe it should be called "quantitative epistemology".
Ma questa volta sembra abbastanza convincente.
E' quasi un secolo, ormai, che la meccanica quantistica continua a reggere contro tutti i tentativi di attacco sperimentale, mentre il fastidio "filosofico" che si prova a maneggiarla non si è ridotto punto. Ebbene, leggendo Aaronson si ha davvero la sensazione che i metodi della computer science possano finalmente offrire possibilità concrete per aprire una breccia proprio sul lato concettuale dei problemi. Ma è solo un paradosso, non c'è contraddizione: da una parte davvero la teoria della computabilità guarda alla meccanica quantistica da un punto di vista squisitamente teorico, e tuttavia, ugualmente, lo spirito è innegabilmente galileiano, quello con cui si parte da casi concreti e problemi circoscritti, per lasciar comporre alle loro risposte, le risposte alle domande più generali sui massimi sistemi:
Now that we have quantum computing, can we bring the intellectual arsenal of computational complexity theory to bear on this sort of question? I hate to disappoint you, but we can't resolve this debate using computational complexity. It's not well-defined enough. Although we can't declare one of these views to be the ultimate victor, what we can do is to put them into various "staged battles" with each other and see which one comes out the winner. To me, this is sort of the motivation for studying all sorts of questions about quantum proofs, advice, and communication.
Buona lettura!

15 February 2008

Shtetl-Optimized

Finalmente!
Dopo tanto tempo Scott Aaronson si è deciso a proseguire con la pubblicazione delle lectures del suo Quantum Computing Since Democritus: è da poco online la lezione numero 12.
Di più, ora inizia un nuovo corso, Great Ideas in Theoretical Computer Science, di cui è già disponibile la prima lezione.
Altre letture per i miei lunghi viaggi in treno! :)

22 November 2007

Probabilità negative 2: dalla probabilità ad uno spazio lineare (e poi daccapo)

Riprendo il discorso da dove l'avevo lasciato, qui, sulla lezione 9 di Aaronson.
   —   ∴   —   
Il percorso ingannevole parte con la rimozione della condizione di normalizzazione per una distribuzione di probabilità. Poiche' tale condizione si traduce semplicemente in un riscalamento complessivo di tutte le probabilità con un fattore costante globale, univocamente determinato dalla distribuzione stessa, si puo' sempre pensare di procedere senza questo vincolo e riapplicarlo solo alla fine quando bisogna confrontare le probabilità con le effettive frequenze misurate sperimentalmente. Del resto il concetto di probabilità nasce proprio come frequenze normalizzate, le frequenze essendo semplicemente non-negative.
 
Se si procede a questa sorta di semplificazione o di generalizzazione del concetto di probabilità, una distribuzione di probabilità si trasforma da combinazione lineare convessa a combinazione lineare non-negativa, sui possibili esiti. Da qui a chiedere di rimuovere anche il vincolo di non-negativita' delle componenti, fino ad ottenere un vero e proprio spazio lineare di probabilità, il passo e' breve (almeno per Aaronson).
Si noti, però, che il carattere di spazio lineare è del tutto innaturale per uno spazio di probabilità: le distribuzioni di probabilità non si sommano fra di loro nè si fanno combinazioni lineari. La mossa verso uno spazio lineare, in questo ragionamento, è una mossa dettata completamente a posteriori dal fatto che uno spazio lineare sarà la base della meccanica quantistica (gli stati fisici, quelli sì, si sommano, ovvero si sovrappongono).
 
Le ampiezze complesse della meccanica quantistica sono legate al suo carattere probabilistico e "somigliano" alle probabilità stesse, ma il loro carattere lineare è completamente estraneo al tradizionale concetto di probabilità. Il passaggio presuppone, dunque, non solo un'estensione di dominio (da reale-non-negativo a complesso) ma un vero e proprio salto di struttura matematica. E' diffile accettare questo salto semplicemente come una "naturale generalizzazione" piuttosto che come un'analogia forzata.
 
Ma torniamo a questa presunta generalizzazione. In ogni caso queste componenti della combinazione lineare (non piu' non-negativa ne' convessa) non possono piu' essere interpretate direttamente come probabilità, ovvero messe a diretto confronto con le frequenze misurate sperimentalmente. Allora si decide di ricostruire una distribuzione di probabilità tramite un meccanismo di ri-non-negativizzazione (l'applicazione del modulo-quadro) di quelle componenti e, risalendo a ritroso, di ri-normalizzazione. E arriviamo dunque ad una 2-norma del vettore dello spazio lineare precedentemente costruito.
 
E' chiaro che tale procedimento, partito in qualche modo come semplificazione per il calcolo matematico (l'applicazione di un vincolo solo in fase finale) e dunque di carattere del tutto arbitrario e convenzionale, finisce per originare una struttura del tutto nuova (lo spazio lineare delle ampiezze) su cui imbastire uno spazio di probabilità esattamente identico a quello che si intendeva semplificare e/o generalizzare (fatto di componenti non-negative e normalizzate, il modulo quadro di quelle ampiezze).
 
Insomma, il concetto di probabilità non viene in alcun modo generalizzato (si tratta sempre di un'astrazione del limite per delle frequenze misurate sperimentalmente), ma semplicemente innestato su un substrato di spazio lineare che pretende di costituire il fondamento per l'evoluzione temporale e la combinazione di quelle distribuzioni di probabilità. Ovvero, pretende di costituire la fisica che soggiacie alle probabilità misurate sperimentalmente, esattamente come la fisica classica costituiva il substrato fisico per le distribuzioni di probabilità sperimentali, prima dell'analisi dei fenomeni atomici e microscopici. Con l'avvento della meccanica quantistica ci si è resi conto che le distribuzioni di probabilità sperimentalmente misurate (le distribuzioni di frequenze) devono essere descritte con un formalismo basato su uno spazio lineare. Ci si è poi resi conto che questa nuova fisica "lineare" aveva proprietà molto strane rispetto a qualsiasi cosa si fosse abituati (entanglment, disuguaglianze di Bell) e che fosse intrinsecamente probabilistica (differenza fra miscele statistiche e sovrapposizioni coerenti).
 
Ma tutto ciò ha a che fare con la fisica, non con la probabilità.

16 October 2007

probabilità negative, ovvero: non poteva che essere meccanica quantistica

La Meccanica Quantistica è quello a cui si arriva inevitabilmente se si parte dalla teoria della probabilità e si prova poi a generalizzarla in maniera che i numeri che usualmente chiamiamo "probabilità" possano essere negativi. In questi termini, la teoria avrebbe potuto essere inventata dai matematici nel XIX secolo senza alcun input sperimentale. Non è stato così, ma avrebbe potuto essere.
Eppure, con tutte le strutture studiate dai matematici, nessuno di essi è giunto alla meccanica quantistica finchè l'esperimento non l'ha costretto.
Questa è una perfetta esemplificazione del perchè gli esperimenti sono importanti. Quasi sempre l'unico vero motivo per cui abbiamo bisogno degli esperimenti è che non siamo abbastanza acuti. Una volta effettuati gli esperimenti, se abbiamo imparato qualcosa che valeva la pena sapere, è — si spera — proprio il perchè non era necessario partire con un esperimento, perchè non avrebbe avuto senso che il mondo fosse altrimenti. Ma eravamo troppo ottusi per capirlo da soli!
Scott Aaronson, PHYS771, Lecture 9
(mia libera traduzione)
 
Mi sarebbe piaciuto condividere, ma in fondo le cose non stanno proprio così.
   —   ∴   —   
Intendiamoci, i termini generali di una posizione simile sono del tutto condivisibili (hai la sensazione di aver capito davvero proprio quando ti accorgi che le cose non potevano essere altrimenti) e non esiterei a sottoscriverli per il caso della Relatività Speciale (e del resto Einstein non era partito affatto dai risultati dell'esperimento di Michelson-Morley) e forse ancor di più per la Relatività Generale. Ed è anche vero, per citare la teoria dell'evoluzione menzionata da Aaronson, che sebbene Darwin giunse alla sua intuizione dopo un prolungato periodo di osservazione della fauna delle Galapagos, tuttavia non ebbe bisogno di appoggiarsi alla teoria di Mendel sull'ereditarietà dei caratteri nè di conoscere il dogma centrale della biologia moderna che impedisce ai caratteri acquisiti à la Lamark di essere trasmessi alle generazioni successive.
Ma il caso della meccanica quantistica, secondo me, è profondamente diverso, soprattutto se guardato dal punto di vista che propone Aaronson, quello della probabilità.
Il concetto di probabilità nasce in simbiosi con quello di frequenza e non ha senso parlare di probabilità negativa neanche in meccanica quantistica. La novità matematica alla base della meccanica quantistica che, si sostiene, avrebbe potuto essere "inventata" senza inbeccata sperimentale, non è alcun concetto di probabilità negativa (o addirittura complessa). La novità è uno spazio lineare (con prodotto interno, uno spazio di Hilbert) come substrato dello spazio di probabilità, da cui derivare, cioè, la distribuzione di probabilità stessa come una p-norma dei vettori di quello spazio. Ma questa idea non ha alcun carattere di necessità, una teoria della probabilità non ha alcun bisogno di ergersi su uno spazio lineare. E del resto la meccanica quantistica vede in tale spazio lineare la natura fisica del mondo, un modello di realtà che, tra le altre cose, presenta caratteri di aleatorietà da descrivere per mezzo di distribuzioni di probabilità del tutto "tradizionali" (reali e non-negative). E se invece dalle solite miscele statistiche siamo arrivati a dover maneggiare cose terribili come le sovrapposizioni coerenti e le violazioni delle disuguaglianze di Bell (cose che nessun filosofo che si fosse divertito a distinguere fra probabilità epistemica e non-epistemica avrebbe comunque mai potuto immaginare), è perchè abbiamo dovuto fronteggiare una nuova fisica, non perchè abbiamo scoperto nuove proprietà matematiche del concetto di probabilità.
Certo, una volta accettata l'idea di uno spazio lineare da cui derivare distribuzioni di probabilità, ci sono ragioni di consistenza intrinseca e naturalezza che conducono a nient'altro che una 2-norma su uno spazio di Hilbert su campo complesso. E per questo vale assolutamente la pena di leggere la lezione 9 di Aaronson. Ma pensare che, per questo, il mondo non poteva non realizzare altro che la teoria della meccanica quantistica, significa non rendersi conto che la meccanica quantistica non è una teoria della probabilità, ma una teoria che fa uso della teoria della probabilità.
Al di là della questione particolare sollevata da Aaronson, comunque, siamo ancora ben lontani da una comprensione della meccanica quantistica à la "non poteva che essere così!". Ma forse non è questione di comprensione quanto, banalmente, che non siamo ancora arrivati alla teoria che "non poteva che essere così!"...

05 June 2007

NP-complete Problems and Physical Reality - 2

Ora, una delle congetture piu' ambiziose e difficili da dimostrare e' proprio quella secondo cui non esistono algoritmi capaci di risolvere i problemi NP-completi in un tempo polinomiale. E l'articolo di Aaronson [›››] affronta esattamente tale questione, ma spostando l'attenzione da un punto di vista strettamente algoritmico ad uno piu' squisitamente fisico. La domanda e': non e' che l'impossibilita' di risolvere efficientemente i problemi NP-completi costitusce una vera e propria limitazione fisica nel nostro universo, esattamente come il limite della velocita' della luce o, forse meglio, come la seconda legge della termodinamica?
Vengono dunque passati in rassegna diversi tipi di dispositivi fisici che possono essere pensati e/o sono stati proposti, almeno in linea di principio, come calcolatori "naturali" capaci di rislovere, eventualmente specifici, problemi. A partire dal caso forse piu' famoso, quello delle bolle di sapone.
   —   ∴   —   
Avete i vostri n punti disposti su un piano e cercate l'insieme di segmenti, di lunghezza complessiva la piu' piccola possibile, che uniscano tutti i punti che avete scelto (i segmenti possono anche incontrarsi in altri ulteriori vertici rispetto ai punti scelti). Si puo' mostrare che questo tipo di problema e' proprio di tipo NP-completo. E puntualmente tutti gli algoritmi di soluzione finora proposti sono in grado di trovare la soluzione in un tempo che cresce esponenzialmente col numero di punti da collegare. Ora, e' un classico esempio di folklore scientifico quello di mostrare come sia possibile trovare la soluzione a un problema di questo tipo utilizzando delle bolle di sapone. Prendete due lastre di vetro tenute parallele da una serie di pioli fissati su entrambe le lastre proprio nelle posizioni dei punti del piano che avevate scelto. Immergendo le due lastre in un bagno di acqua e sapone, e poi risollevandole, e' possibile leggere la soluzione a questo problema nelle lamine di acqua e sapone che si formano tra i pioli (e la spiegazione e' che le bolle di sapone, per questioni energetiche, tendono a minimizzare la propria superficie...). Ora il punto in gioco non e' neanche quello che le bolle di sapone possono fare piu' di un calcolatore tradizionale (macchina di Turing). Si puo' infatti dimostrare che la fisica classica (delle lamine di acqua e sapone) puo' essere simulata per mezzo di "semplici" algoritmi polinomiali. Un esperimento di fisica, dunque, vorrebbe essere nientepopodimenoche' la dimostrazione che esiste un algoritmo tradizionale capace di risolvere un problema NP-completo in tempo polinomiale (pur non fornendo alcun esempio di tale algoritmo).
In realta' non c'e' nessuno scoop, perche', di fatto, non e' vero che l'esperimento delle bolle di sapone e' un buon metodo per risolvere il problema posto. O almeno non sempre. Quello che succede, infatti, e' che le lamine che si formano immergendo le lastre nell'acqua e sapone semplicemente tendono a rilassarsi verso una configurazione piu' stabile che minimizzi la loro superficie (e quindi la lunghezza complessiva dei segmenti corrispondenti). Ma non e' affatto detto che questo processo di assestamento si concluda nella configurazione ottimale in assoluto. Con pochi punti, questo e' quello che (spesso) succede davvero, ma aumentando pian piano il numero di pioli fra le lastre si osserva proprio che la formazione di lamine e' quasi del tutto casuale e, pur con occasionali "semplificazioni" verso configurazioni energeticamente piu' convenienti, risulta tutt'altro che la piu' conveniente.
Del resto c'e' tutta una classe di algoritmi tradizionali che tentano di risolvere istanze di problemi NP-completi proprio attraverso meccanismi di rilassamento verso "stati di minima energia" (come i vetri di spin). La difficolta' di questi algoritmi e' proprio quella della presenza di minimi locali che "intrappolano" l'esplorazione dello spazio delle soluzioni e fanno crescere esponenzialmente i tempi di rilassamento verso la soluzione ottimale cercata.
   —   ∴   —   
Interruzione, penserete voi, significa che sta passando ad un'altro dispositivo o fenomeno fisico. Invece no, c'e' un'ultima cosa da dire su questo punto. E lo stacco grafico ha il solo scopo di consentirmi di dare il necessario rilievo a quello che, secondo me, rappresenta uno dei passaggi piu' profondi dell'articolo di cui sto parlando. Un passaggio che consta di un paio di frasette buttate li' quasi semplicemente a concludere l'argomento, e che hanno invece provocato in me quella straordinaria sensazione che si prova quando si capisce qualcosa di semplice e profondo allo stesso tempo. Seguitemi.
Un esempio del tutto analogo a quello dei vetri di spin e delle bolle di sapone e' quello del ripiegamento delle proteine. Per quello che dicevamo sulla definizione della classe di problemi NP-completi, si potrebbe addirittura pensare di utilizzare delle proteine artificiali come calcolatori, mappando opportunamente la disposizione degli amminoacidi con i vincoli del nostro problema in maniera tale che la configurazione ripiegata della proteina fornisca una codifica per la soluzione al nostro problema di partenza. Ebbene, esattamente come nel caso delle bolle di sapone, nessuno puo' garantirci che il processo di ripiegamento della proteina artificiale non si "incagli" in minimi locali ben lontani dalla vera configurazione di minimo energetico.
Vi e' sorta spontanea la domanda centrale? Come diavolo fanno allora le proteine naturali a ripiegarsi correttamente in tempi rapidissimi? Vi siete gia' risposti? Evidentemente le proteine naturali si sono evolute specificatamente proprio per evitare di incontrare nel processo di ripiegamento, o di avere del tutto, minimi locali in cui incastrarsi (ed eccezioni a questa regola di buon adattamento sono date, per esempio, dai prioni...). [›››]

30 May 2007

NP-complete Problems and Physical Reality − 1

Personalmente ho letto tutto l'articolo [›››] senza ricordarmi cosa fossero esattamente i problemi NP-completi. Se volete essere precisi potete andare sulla wikipedia oppure, molto meglio, potete divertirvi leggendo le lezioni di Aaronson (la quinta e la sesta in particolare, ma a quel punto il consiglio e' di partire dall'inizio...) dove l'ho ri-scoperto io stesso, dopo. Se siete pigri come me, puo' bastare sapere che con l'espressione NP-completi si fa riferimento ad una classe di problemi difficili, dove il concetto di difficolta' puo' essere espresso in maniera tecnicamente piu' precisa (ho scoperto che c'e' un variegatissimo zoo di classi di complessita'...).
In generale i problemi considerati sono caratterizzati da una grandezza variabile n (le cifre del numero da fattorizzare, la lunghezza della proteina da ripiegare...) e gli algoritmi che vengono proposti per risolvere tali problemi sono caratterizzati dalla maniera con cui scalano, all'aumentare di n, le risorse computazionali (memoria, tempo...) richieste dall'algoritmo per risolvere il problema. Ad esempio, un modo di vedere la difficolta' dei problemi NP-completi passa per la constatazione che qualsiasi algoritmo finora proposto per la loro soluzione richiede un tempo che cresce esponenzialmente con n. La definizione della classe di problemi NP-completi non fa esplicito riferimento allo scalare delle risorse richieste per la soluzione. Del resto quella e' una caratteristica di un algoritmo piu' che di un problema. Questo punto di come definire la "classe di difficolta'" di un problema senza far esplicito riferimento al "miglior algoritmo capace di risolverlo" e' molto interessante, lasciatemi spendere qualche parola in piu' (ma ovviamente sto semplicemente seguendo la lezione 6 di Aaronson...!).
   —   ∴   —   
Considerate il problema di saper dire, di un numero a n cifre, se e' primo o composto (senza necessariamente fattorizzarlo). Oppure considerate il problema di soddisfare il meglio possibile le richieste di alloggio in stanze doppie di un numero n di persone, ciascuna con l'indicazione di quale delle altre persone e' il suo "compagno di stanza preferito". Oppure ancora considerate il problema di sapere, date due sequenze di DNA lunghe n basi, quante inserzioni e rimozioni di basi sono necessarie per convertire una sequenza nell'altra. Ebbene, per questi problemi apparentemente difficili sono invece stati trovati (spesso dopo dozzine di anni di lavoro) algoritmi capaci di risolverli in un tempo polinomiale (un tempo cioe' che cresce "solo" come n ad una qualche potenza). Come possiamo distinguere, dunque, i problemi davvero difficili da quelli che semplicemente sembrano difficili?
Ebbene, uno dei risultati fondamentali della teoria di NP-completezza sviluppata nei primi anni 70 da Cook, Karp e Levin e' proprio il seguente: e' possibile dimostrare, per la maggior parte dei problemi "difficili", che essi rappresentano problemi della stessa difficolta'. Se fossimo in grado, cioe', di risolvere in tempo polinomiale uno solo di questi problemi, allora saremmo automaticamente in grado di fornire un algoritmo polinomiale anche per ciascuno degli altri problemi. Proprio come se ciascuno di essi fosse in realta' nient'altro che la riformulazione di un solo stesso problema.

03 April 2007

Meccanica Quantistica, questa sconosciuta...

Come al solito le tentazioni piu' irresistibili arrivano legioni proprio quando meno puoi permettertelo.
E' da pochissimo che ho aggiunto i feed di questo blog fra i miei segnalibri, e oggi mi sono ritrovato con questo post che mi ha fatto scivolare irrimediabilmente a leggere la lezione 11 [›››] e quindi anche la lezione 9...
Sono in ritardo sparato col lavoro, e proprio non ho tempo, ma − diavolo! − quanto avrei voglia di mettermi a leggere, ora, subito, adesso e tutti di filato, tutte le Further Reading citate in quest'ultima lezione!!!
Per ora mi limito a consigliarvi queste due lezioni, ma quanto prima (sigh!) approfondiro' la cosa: cerchero' di capire meglio chi e' questo Scott Aaronson, daro' sicuramente un'occhiata alle altre lezione del suo corso [›››], al suo apparentemente portentoso articolo e agli altri che cita, compreso questo e gli altri di questo tal Christopher A. Fuchs...
Come si fa a tornare a lavorare?!?
 
PS
Franco, qui c'e' pane anche per i tuoi denti!