La relazione ha un carattere introduttivo.  Prima di tutto verranno presentati alcuni interessanti risultati e problemi aperti della Computer Science.  Quindi verranno definiti i problemi di ottimizzazione combinatoria, tema centrale della Complessità  Computazionale, e verrà  mostrato come possono essere trasformati in problemi di vetri di spin a temperatura nulla.  Il legame tra Meccanica Statistica, Computer Science e Teoria dei Grafi sarà  ampiamente dibattuto. Infine verranno presenti alcuni recenti risultati analitici e numerici, che fanno luce sulle transizioni di fase che avvengono nei problemi di ottimizzazione combinatoria e che soprattutto forniscono una prima chiara interpretazione della nascita della complessità  computazionale in tali problemi.  La relazione si concluderà  con un accenno alle possibili applicazioni e sviluppi futuri.