COMPUTATIONAL COMPLEXITY

Obiettivi formativi

Obiettivi generali: Il corso propone: (1) lo studio di un approccio moderno alla complessità computazionale, (2) la comprensione del concetto di computazioni algoritmiche in presenza di risorse di calcolo limitate e (3) la classificazione dei problemi matematici in base alle risorse necessarie e sufficienti per risolverli algoritmicamente. Si affronta lo studio e la comprensione di problemi fondazionali dell'Informatica e della Matematica come P vs NP e altri problemi affini su altri classi di complessità . Il focus del corso è orientato a studiare problemi intrattabili con risorse computazionali limitate: il fine è quello di acquisire le principiali tecniche matematiche per dimostrare che certi problemi non possono essere risolti con risorse computazionali limitate. Obiettivi specifici: Conoscenza e comprensione: Classificazione dei problemi matematici in base alla risorse e ai modelli di calcolo necessari e sufficienti per risolverli algoritmicamente efficientemente: tempo di esecuzione, memoria, randomness, non determinismo, parallelismo. Tecniche per la dimostrazione che alcuni problemi sono intrattabili avendo a disposizione risorse computazionali limitate. Applicare conoscenza e comprensione: Dotare lo studente delle capacita di problem solving applicato a problemi computazionali principalmente sotto due aspetti: (1) Pensare e descrivere una la soluzione di un problema ad alto livello descrivendone le idee portanti e le motivazioni di efficacia per la soluzione; (2) essere in grado di dettagliare e scrivere matematicamente soluzioni precedentemente descritte ad alto livello. Capacità critiche e di giudizio: Essere in grado di valutare la qualità e la correttezza di soluzioni a problemi di natura computazionale. Capacità comunicative: Descrivere e presentare correttamente problemi di natura computazionale e loro soluzioni matematiche a vari livelli: (1) brevi presentazioni orali della durata di 30 minuti; (2) presentazioni orali matematicamente dettagliate della durata di una o due ore; (3) scrittura scientifica di report con la soluzione di un problema. Capacità di apprendimento: Approfondimento autonomo di alcuni argomenti presentati nel corso, lavoro di gruppo, applicazione concreta delle nozioni e delle tecniche apprese durante il corso.

Canale 1
NICOLA GALESI Scheda docente

Programmi - Frequenza - Esami

Programma
1. Preliminari su Classi di Complessità [2 settimane] 1.1 Modelli teorici di computazione. Risorse computazionali: tempo e spazio. 1.2 Classi di complessità di Tempo e Spazio 1.3 Il problema P versus NP 1.4 NP e NP-completezza 1.5 Problemi non trattabili quando le risorse computazionali sno limitate 1.6 Classi di Complessità: L, NL, P, NP, PSPACE, BPP, RP, #P, IP, 1.7 risultati principali 2. Diagonalizzazione[1 settimana] 3. Teoremi di Gerarchia[1 settimane] 4. Resultati di Barriera I: Diagonalizzazione non è sufficiente per provare P diverso da NP [1 settimana] 5. Complessità spaziale [2 settimane] 5.1 Teorema di Shamir: PSPACE = IP 5.2 Teorema di Immerman-Szelepcsényi : NL=coNL, 6. Circuiti Booedani [2 settimane] 6.1 Definizioni preliminari e circuiti efficienti 6.2 Circuiti con profondità costante: Gerarchie NC e AC. 6.3 Teorema di Hastad-Razborov-Smolensky: Parità richiedi circuiti a profondità costante di dimensione esponeziale. 6.4 Circuiti Monotoni 7. Gerarchia Polinomiale e teoremi fondamentali [1 settimana] 8. Resultati di Barriera - II [1 settimana, opzionale] 8.1 Teorema di Rudich-Razborov: "Natural proofs" non sono sufficienti per separare P da NP (a meno di rompere protocolli crittografici sicuri) 9. Altri modelli di of computations e loro limiti: [1 settimana] 9.1 Alberi di Decisione 9.2 Branching programs. 10. Introduzione alla Complessità delle dimostrazioni [2 settimane] 10.0 Relazione con il problema P versus NP 10.1. Sistemi Logici: Resoluzione 10.2 Sistemi Geometric: tagli di Chvatal 10.3 Sistemi Algebrici: Polynomial Calculus 10.4 sistemi Semialgebraici: Sherali-Adams and Sum-of-Squares 10.5 Limiti inferiori esponenziali per Resolution and Cutting planes: metodo Ben-Sasson-Wigdeson e Interpolazione trattabile
Prerequisiti
Concetti di base di Matematica Discreta (conteggi, grafi, permutazioni, ) [importante] Concetti di algoritmo e di strutture dati (pile, code, alberi)[importante] Algoritmi efficienti in presenza di informazioni aggiuntive (esempio ricerca binaria) [importante] Nozioni di base di Logica proposizionale[importante] Concetto di Relazione di arità generica[importante] Concetti di Quantificatore esistenziale ed universale[importante] Nozioni di base di Logica del primo ordine [importante] Nozioni di Linguaggi[importante] Modelli di computazione [importante] Nozioni di Base di Complessità [importante]
Testi di riferimento
S. Arora B. Barak: Computational Complexity: A Modern Approach Cambridge University Press, 2007 O. Goldreich. P, NP, and NP-Completeness: The Basics of Computational Complexity Cambridge University Press 2010 O. Goldreich. Computational Complexity: A Conceptual Perspective Cambridge University Press 2008. A. Wigderson. Mathematics and Computation. Princeton University Press. In press C. Papadimitriou. Computational Complexity. Pearsons. 1994. S. Jukna. Boolean Function Complexity. Springer. 2012 H. Vollmer. Introduction to Circuit Complexity: an uniform approach, Springer. 2013 J. Krajicek. Proof Complexity. Cambridge. 2019.
Frequenza
non obbligatoria
Modalità di esame
Per superare l'esame occorre conseguire un voto non inferiore a 18/30. Lo studente deve dimostrare di aver acquisito una conoscenza sufficiente degli argomenti trattati, e di essere in grado autonomamente di collegare tra loro i diversi argomenti. Per conseguire un punteggio pari a 30/30 e lode, lo studente deve invece dimostrare di aver acquisito una conoscenza eccellente di tutti gli argomenti trattati durante il corso, essendo in grado di raccordarli in modo logico e coerente. In fase di valutazione dell'esame si terrà conto dei seguenti aspetti: (1) la logica seguita dallo studente nella risoluzione dei quesiti osti ; (2) la correttezza della procedura individuata per la soluzione dei quesiti; (3) l'adeguatezza della soluzione proposta in relazione alle competenze che lo studente si presuppone abbia acquisito alla fine del corso; (4) l'impiego di un linguaggio Italiano (o inglese se l'esame è in Inglese) appropriato. Si terrà conto anche (1) della capacità di elaborare una risposta adeguata alle domande poste, (2) della capacità di prontezza dello studente di rispondere correttamente alle domande. (3) Verranno valutate inoltre la capacità dello studente di inferire nuova conoscenza a partire dalle nozioni acquisite nel corso
Modalità di erogazione
Il modello didattico adottato è quello della lezione frontale integrato li dove possibile da (1) esercitazioni ( che hanno la forma di soluzioni di problemi concreti data la natura teorica del corso), (2) lavori di gruppo (3) flipped-classroom nel caso in cui gli studenti ricevono esercizi da risolvere a casa. (4) Interrogazioni Durante le lezioni, li dove possibile ed utile, si useranno supporti hardware e software dedicati (per esempio MentiMeter) per stimolare l'attenzione e l'apprendimento e per dare allo studente una idea della evoluzione del suo apprendimento degli argomenti del corso. La lezione viene normalmente divisa in due parti con una pausa di 10 minuti tra una parte e l'altra. Tutto il materiale del corso (slide, comunicazioni, videolezioni, esercitazioni, soluzioni) e tutta la gestione del corso viene settimanalmente caricata sulla pagina del corso predisposta dal docente sula piattaforma Elearning Sapienza
  • Codice insegnamento10612389
  • Anno accademico2025/2026
  • CorsoEngineering in Computer Science and Artificial Intelligence - Ingegneria Informatica e Intelligenza Artificiale
  • CurriculumCurriculum unico
  • Anno1º anno
  • Semestre2º semestre
  • SSDING-INF/05
  • CFU6