Showing posts with label NP-complete Problems and Physical Reality. Show all posts
Showing posts with label NP-complete Problems and Physical Reality. Show all posts

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.