Fondamenti dell'Informatica: Complessità

La complessità computazionale è uno dei più affascinanti campi di ricerca dell'informatica e più in genere delle scienze, volto sia allo studio del costo computazionale nella soluzione algoritmica di problemi sia ad una classificazione dei problemi in base a questo costo, secondo opportune misure di complessità (tempo/spazio). Questa classificazione permette di studiare la difficoltà intrinseca di classi di problemi di largo interesse nella pratica comune dell'informatica ed i limiti conosciuti per il raggiungimento di buoni algoritmi per risolvere problemi complessi. In quest'area si trova uno dei problemi più affascinanti rimasti tutt'ora aperti nel campo delle scienze esatte: l'ormai noto problema P $\stackrel{?}{=}$ NP. Oltre a rappresentare un interessante campo di ricerca, la complessità computazionale è al tempo stesso anche un prerequisito per molti settori avanzati dell'informatica, come l'intelligenza artificiale, la logica ed i fondamenti dell'informatica, l'analisi e la verifica di programmi, la criptografia, i sistemi distribuiti e le reti di calcolatori, ecc. Questo corso è rivolto non solo agli studenti che abbiano interessi in tali settori, ma anche a quanti vogliano approfondire e sistematizzare in un quadro concettuale rigoroso i concetti e le osservazioni sulla complessità degli algoritmi incontrati in corsi precedenti.

Programma del corso:

• Problemi: REACHABILITY, MAX FLOW, TRAVELLING SALESMAN e HAMILTON CIRCUIT.
• Definizione di Macchina di Turing, Macchina di Turing a nastri multipli, Macchina di Turing con Input e Output, Macchina di Turing non-deterministica.
• Simulazione di M.d.T. a nastri multipli con M.d.T. ad un nastro con perdita polinomiale di efficienza nel tempo d'esecuzione.
• Notazione O(f(n)) e Teorema speedup. Simulazione di M.d.T. nondeterministche con M.d.T. deterministiche con perdita esponenziale di efficienza nel tempo d'esecuzione.
• Espressioni Booleane e circuiti Booleani. Problemi: SATISFIABILITY, CIRCUIT VALUE e CIRCUIT SAT.
• Concetto di classe di complessità e funzione propria di complessità. Teorema del Gap.
• Classi L, NL, P, NP, PSPACE, NPSPACE e EXP. Teorema della gerarchia temporale e spaziale, relazioni fra classi di complessità. Teorema di Savitch, PSPACE = NPSPACE.
• Concetto di riduzione $log n$-space. Riduzione di HAMILTON PATH a SATISFIABILITY. Composizione di riduzioni. Completezza: CIRCUIT VALUE è P-completo. Teorema di Cook SATISFIABILIY è NP-completo. Alcuni esempi di problemi P-completi ed NP-completi.
• La classe co-NP: PRIMES è in NP ed in co-NP
• Struttura nota delle classi
• Cenni di criptografia.

Testo di referenza: C. Papadimitriou. Computational Complexity, Addison Wesley, 1995.