Prof. Alessandro Berarducci
 

Teoria descrittiva della complessità computazionale, teoria dei
modelli finiti Verrà approfondito lo studio delle classi di complessità computazionale. Una certa conoscenza della teoria degli algoritmi della calcolabilità (che può essere acquisita in un corso di programmazione e in parte nel primo modulo di logica) è consigliata ma non richiesta. Verrà dato ampio spazio alla teoria ``descrittiva'' della complessità la quale mette in relazione la complessità algoritmica di un problema con la complessità della sua descrizione in opportuni formalismi logici. In questo approccio gioca un ruolo importante la ``teoria dei modelli finiti''. Bibliografia: C. H. Papadimitriou, Computational complexity, Addison-Wesley, 1994. N. Immerman, Descriptive Complexity, Springer, 1998. H.-D. Ebbinghaus, J. Flum, Finite Model Theory, 1991. --