COMPLESSITÀ       a.a. 2009/10

Programma di massima del Corso

Nozioni di base

Algoritmi, efficienza, problemi di ottimizzazione, problemi di decisione, la classe P, la classe NP, la questione P=?NP, riduzioni polinomiali e problemi NP-completi, il teorema di Cook-Levin, NP-completezza dei problemi 3SAT, Copertura con nodi, Insieme indipendente, 3-colorazione, il problema del taglio, e il problema dello zaino, algoritmo pseudopolinomiali.
 

La complessità dei problemi di ottimizzazione

Le classi NPO e PO, algoritmi d'approssimazione e rapporto d'approssimazione. Esempi: la massima soddisfacibilità, la copertura minima con nodi, la copertura minima d'un insieme, il massimo insieme indipendente, il problema del commesso viaggiatore con diseguaglianza triangolare, il problema del massimo taglio, il problema dello zaino. Le classi APX, PTAS e FPTAS. Limiti dell?approssimabilità e la tecnica del gap. Se P ⊂ NP allora PO ⊂ FPTAS ⊂ PTAS ⊂ APX ⊂ NPO. Riduzioni che preservano l'approssimabilità. Il teorema PCP e la sua applicazione per provare risultati di non approssimabilità, esempi: MAX-3SAT e Cricca.
 

Algoritmi e classi probabilistiche

Esempi: il problema del taglio minimo, 2SAT, verifica del prodotto di matrici, verifica dell'identità di polinomi. il problema del perfect matching, il test di primalità. Approssimazione randomizzata: il problema del massimo taglio, il problema della massima soddisfattibilità. Le classi PP, BPP, RP, e ZPP, loro relazione con le classi P, NP e PSPACE. Amplificazione della probabilità di successo.
 

La gerarchia polinomiale

Le classi Σ_k, Π_k, e PH e loro caratterizzazioni. Alcune proprietà: BPP contenuta in Σ₂. Se NP = co-NP allora PH = NP. Se Σ_k =Π_k allora PH finita. Se PH infinita allora PH ⊂ PSPACE.
 
 
 

Testi Consigliati

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, (Jackson libri)
2. Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, Protasi, Complexity and Approximation, Springer
3. O. Goldreich, Introduction to Complexity Theory, 1999, disponibile online: http://www.wisdom.weizmann.ac.il/~oded/cc99.html
4. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.
5. Christos H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1995.
6. D. P. Bovet e P. Crescenzi Teoria della Complessità Computazionale, (Franco Angeli) 1991.
7. J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, (Addison Wesley) 2001.
8. S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, disponibile online: http://www.cs.princeton.edu/theory/complexity/

---