Computational Complexity
Insegnamento: Computational Complexity
Titolo insegnamento in inglese: Computational Complexity
Lingua: italiano
Anno di corso: 1
Semestre: 2
CFU: 6
Insegnamenti propedeutici previsti: Nessuno.
Docenti:
- Piero Andrea Bonatti
Obiettivi Formativi
Questo corso estende e completa la preparazione algoritmica spostando l'attenzione dalla complessità dei singoli algoritmi alla complessità intrinseca dei problemi, espressa rispetto alle risorse computazionali necessarie per la loro risoluzione. In questo modo si apprendono criteri per stimare l'ottimalità degli algoritmi, si identificano tecniche comuni per la risoluzione sistematica di ampie classi di problemi, si acquisiscono approcci più scientifici alla risoluzione di nuovi problemi. Verranno spiegate le relazioni tra consumo di memoria e lunghezza della computazione e il ruolo del nondeterminismo nell'analisi dei problemi la cui complessità esatta non è nota. Verranno altresì analizzate le relazioni tra questi aspetti e aree applicative importanti quali crittografia, ricerca operativa e ottimizzazione combinatoria, quantum computing.
Programma
Problemi e algoritmi: formulazioni intuitive e formalizzazioni mediante linguaggi e macchine di Turing multinastro. Misure appropriate di complessità in termini di spazio e di tempo. Teoremi di speedup. Confronti con altre formalizzazioni delle computazioni e tesi di Church (cenni). Classi di complessità, teoremi di gerarchia e teorema di Savitch. Riduzioni e completezza come formalizzazioni delle difficoltà relative e della complessità caratteristica dei problemi. Alcuni risultati di separazione. Problemi logici, su grafi e su insiemi completi per NP e coNP. Teorema di Cook. La gerarchia polinomiale e PSPACE. Relazioni con la crittografia moderna. Breve analisi dell'impatto del quantum computing sulla risoluzione di problemi e sulla crittografia. Cenni delle classi oltre PSPACE: problemi che richiedono risorse esponenziali e problemi indecidibili.
Modalità didattiche
Lezioni frontali. Esercitazione.
Materiale didattico
Christos H. Papadimitriou, Computational complexity. Addison-Wesley 1994, ISBN 978-0-201-53082-7, pp. I-XV, 1-523
Modalità di esame
L'esame si articola in prova scritta ed orale.
La prova scritta consta di quesiti a risposta multipla e libera.