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...). [›››]
