La Stampa - Consultazione Archivio

Se il computer gira a vuoto TRA LOGICA E FISICA Se il computer gira a vuoto Un 'applicazione informatica dei «vetri di spin» UN gruppo di ricerca composto da Monasson, Zecchina, Kirkpatrick, Selman e Troyansky ha pubblicato recentemente (sulla nviasta «Nature», n. 400, 133-137; 1999) un lavoro che ha attirato l'attenzione degli esperti di informatica e che conferma risultati di rilievo già ottenuti in precedenza da Monasson e Zecchina. Prima di entrare nei dettagli vorrei richiamare alcune nozioni elementari di logica. Una variabile logica ò una quantità, detta booleana, che può prendere solamente il valore "falso" o "vero". Molti rompicapo offerti ai lettori da riviste di enigmistica, la soluzione di un giallo ma anche molti problemi pratici implicano l'assegnazione del valore "falso" o "vero" a una serie di variabili logiche legate tra di loro da clausole che dipendono dal problema considerato e lo definiscono. Nel suo divertente e acuto commento al lavoro di Monasson, il Nobel Philip W.Anderson ricorda i quiz del liceo in cui si dovevano collegare tra di loro tre case, tre cognomi e tre nomi di tre persone in base a una serie di domande ben congegnate. A prima vista di tratta di un rompicapo fatto apposta per trascorrere piacevolmente il tempo in un momento di relax. Immaginiamo tuttavia di avere a che (are con un problema decisionale che coinvolge miliardi di variabili logiche e relative clausole e ci renderemo conto che, senza computer e senza un algoritmo adatto che punti velocemente verso la soluzione la perdita di tempo può diventare di fatto l'eternità. Molti problemi di grande interesse pratico sono effettivamente di questo tipo. Per consultare efficacemente un elenco telefonico occorre poterlo ordinare velocemente in ordine alfabetico oppure secondo il numero di telefono. Se esaminiamo in dettaglio questi problemi ci rendiamo conto che essi richiedono una soluzione in cui occorre decidere se un numero sterminato di variabili logiche legate da un numero paragonabile di clausole sono vere o false. Un problema di grande interesse pratico è quello della ottimizzazione degli orari delle linee aerei;. Problemi importanti hanno diritto a una sigla criptica: in questo caso la sigla ò K-SAT, dove SAT sta per "soddisfabilità" e K denota il numero di variabili booleane legate dalle clausole. Una clausola è vera se lo ò almeno una delle variabili da essa collogato. Solitamente K = 2 o K = 3. Il problema decisionale consiste nel soddisfare tutte le clausole contemporaneamente. Se il numero di clausole è piccolo si trova facilmente una soluzione; se invece e alto non esiste in generale soluzione in cui tutte le clausole sono soddisfatte. Il caso peggiore è quello posto a metà strada tra questi estremi in cui il computer impiega un temilo lunghissimo per arrivare alla meta: si tratta quindi di una configurazione da evitare a tutti i costi nelle applicazioni. Se K >2, in pratica si assume K = 3, i K-SAT richiedono un tempo di computer che cresce in progressione geometrica o esponenziale nel numero di Variabili logiche, detti in gergo NP-compIeti. Il più celebre ed emblematico dei problemi NP-completi è quello affrontato da un commesso viaggiatore che presenta il suo campionario in una serie di città di cui conosco tutte le distanze relative e vuole visitarle nell'ordine in cui il percorso totale è minimo. Il problema del commesso viaggiatore sembra molto semplice ma sconfigge anche i supircomputer più agguerriti se il numero delle città supera il centinaio. Monasson ha esaminato problemi misti in cui una frazione delle clausole è di tipo 3-SAT e le rimanenti di tipo 2-SAT. Se la frazione 3-SAT sta al di sotto di un valore critico ben definito il problema richiede tempi propor¬ zionali al numero di variabili in gioco, andando oltre la soglia i tempi crescono esponenzialmente. La soglia seghala un regime di calcolo in cui il computer impazzito gira in tondo senza raggiungere la meta. La difficoltà che si incontra nel trattare questi problemi non dipende tanto dal numero di vanabili e di clausole quanto dalla vicinanza alla soglia. Giova ripetere che questi risultati si applicano solo a problemi con un numero rilevante di variabili e di clausole ma in ogni caso avranno un impatto profondo sulle future strategie in campo informatico. Di grande interesse è l'identità formale tra questi problemi e altri remoti collegati ai cosiddetti «vetri di spin». In fisica la parola vetro indica strutture amorfe e prive di quella ripetitività e simmetria che caratterizza i cristalli. In questo contesto la parola "cristallo" applicata nel linguaggio comune ai vetri di alta qualità appare fuori luogo, la struttura microscopica del vetro è infatti disordinata. Il vetro di spin è materiale virtuale composto da magneti elementari che puntano solamente in due direzioni, alto e basso, assimilabili al "vero" o "falso" della variabili logiche. Tra i magneti agiscono forze, il cui ruolo è simile a quello delle clausole, che tendono ad allinearli oppure a farli puntare in direzioni opposte. I vetri di spin sono molto popolari tra i fisici perché suscettibili di una trattazione matematica che dà indicazioni utili per lo studio dei sistemi complessi. Variando la temperatura o cambiando le forze tra magneti la struttura fisica del vetro di spin può cambiare in modo discontinuo e macroscopico, passando per quella che i fisici chiamano «transizione di fase». Qualsiasi materiale è soggetto a transizioni di fase se sottoposto a cambiamenti di temperatura, pressione o composizione chimica. L'ebollizione e congelamento dell'acqua sono esempi ben noti di transizioni di fase. Di grande interesse è l'analogia interdisciplinare fra transizione di fase in un vetro di spin e la transizione che appare in un problema K-SAT. Una prima conclusione pratica che si può trarre dalla analogia è che occorre stare lontani da queste transizioni che segnalano configurazioni critiche il cui il computer gira a vuoto senza arrivare a una conclusione. Vorrei chiudere questo articolo con due considerazioni. La prima è che nella scienza le visioni interdisciplinari hanno un ruolo propulsivo fondamentale e che di certo i risultati di Monasson avranno ulteriori applicazioni di rilievo. L'altra è la' soddisfazione personale di vedere Riccardo Zecchina, già ricercatore al Politecnico di Torino, nel plotone d'assalto. Tullio Regge Politecnico di Torino Su «Nature» uno studio interdisciplinare che porta alla ribalta il Politecnico di Torino Un vetro di spin è un aggregato di magnetini, detti irvgergo spin, e simili all'ago di una bussola', ma che possono solamente puntare verso l'alto q verso il basso. La lóro distribuzione spaziale è irregolare e non ripetitiva come gli atomi di un cristallo. Nella analogia tra variabili logiche e spin le frecce che ■ puntano verso l'alto fc^>^. corrispondono al.«vero» --| e le altre al 'falso». \ m wtggi l iiniiiiiiiHiiniiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiitiriiiiitiiiii AmAbkImhI MnèMUnMAaMè mAmmlmiitml ' nAmÀmi Tra spin vicini agiscono forze che tendono ad allinearli (in chiaro) oppure a costringerli in direzioni opposte. Le proprietà di un vetro di spin fatto da un numero di componenti molto alto sono di grande interesse nello studio dei materiali amori). ^^^^^^^^^^^^^^^ -*:ì-* Tra spin vicini agiscono forze che tendono ad allinearli (in chiaro) oppure a costringerli in direzioni opposte. Le proprietà di un vetro di spin fatto da un numero di componenti molto alto sono di grande interesse nello studio dei materiali amori).