Computational Complexity

Sapienza Università di Roma · Ingegneria dell'informazione, informatica e statistica · tutti i canali con docenti, libri e orari, a.a. 2026/2027

Prof. Massimo Lauria Canale unico

Ingegneria dell'informazione, informatica e statistica · esame facoltativo · 6 CFU · apri nel catalogo

Testi principali

Arora – Computational Complexity Vai su Amazon ›

Rao – Communication Complexity and Applications Vai su Amazon ›

Goldreich – Computational Complexity Vai su Amazon ›

Vollmer – Introduction to Circuit Complexity Vai su Amazon ›

Cosa indica di studiare il docente

Argomenti del programma: Questo è il programma dell'anno 2025/2026. Il programma potrà subire leggere variazioni di anno in anno. _________________________________________________ SYLLABUS OF "COMPUTAIONAL COMPLEXITY 2025/2026" Massimo Lauria 1 Bibliography ============== The main textbook of the course is - [AB] Arora, Barak. /Computational Complexity: A Modern Approach/. Cambridge University Press, 2007.

Prof. Nicola Galesi Canale unico

Ingegneria dell'informazione, informatica e statistica · esame facoltativo · 6 CFU · apri nel catalogo

Arora – Computational Complexity Vai su Amazon ›

Goldreich – Computational Complexity Vai su Amazon ›

Vollmer – Introduction to Circuit Complexity Vai su Amazon ›

Cosa indica di studiare il docente

Argomenti del 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.