Computational Complexity – prof. Nicola Galesi

Engineering in Computer Science and Artificial Intelligence - Ingegneria Informatica e Intelligenza Artificiale · Sapienza Università di Roma · 1º anno · 2º semestre · 6 CFU · a scelta (Caratterizzanti ING-INF/05) · canale unico

Testi d'esame di Computational Complexity del prof. Nicola Galesi, canale unico, corso di laurea in Engineering in Computer Science and Artificial Intelligence - Ingegneria Informatica e Intelligenza Artificiale (Laurea magistrale (LM-32)), Sapienza Università di Roma, 1º anno · 2º semestre · 6 CFU · a scelta (Caratterizzanti ING-INF/05), a.a. 2026/2027. Libri adottati: Arora – Computational Complexity; Goldreich – Computational Complexity; Vollmer – Introduction to Circuit Complexity.

Computational Complexity – Prof. Nicola Galesi Canale unico

Corso di laurea: Engineering in Computer Science and Artificial Intelligence - Ingegneria Informatica e Intelligenza Artificiale · Laurea magistrale (LM-32) · 1º anno · 2º semestre · 6 CFU · a scelta (Caratterizzanti ING-INF/05)

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

Il docente indica 1 testo (3 libri tra cui scegliere)

Uno a scelta tra questi 3:

Arora – Computational Complexity Vai su Amazon ›Verificato sulla scheda ufficiale il 18/09/2026

Goldreich – Computational Complexity Vai su Amazon ›Verificato sulla scheda ufficiale il 18/09/2026

Vollmer – Introduction to Circuit Complexity Vai su Amazon ›Verificato sulla scheda ufficiale il 18/09/2026

Bacheca del docente: cosa indica di studiare

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.

Apri la scheda ufficiale ›

Aiutaci a tenerci aggiornati

Il prof ha indicato altri libri, pagine o modifiche? Scrivicelo.

Altre materie del prof. Galesi

Logica e Metodi Probabilistici per L'Informatica · Scienze matematiche per l’intelligenza artificiale · 3º anno · 2º semestre · 6 CFU · a scelta (Gruppo opzionale A)

Altri esami del 1º anno – Engineering in Computer Science and Artificial Intelligence - Ingegneria Informatica e Intelligenza Artificiale

Algorithm Design · 2º semestre · Stefano Leonardi
Computer Vision · 2º semestre · Irene Amerini
Data Management · 2º semestre · Domenico Lembo, Antonella Poggi
Generative Artificial Intelligence · 2º semestre · Fabrizio Silvestri
Innovation Management · 2º semestre · Luca Fraccascia
Interactive Graphics · 2º semestre · Marco Schaerf
Project Management · 2º semestre · Alessandro Annarelli
Artificial Intelligence · 1º semestre · Fabio Patrizi
Cybersecurity · 1º semestre · Leonardo Querzoni, Riccardo Lazzeretti
Dependable Distributed Systems · 1º semestre · Silvia Bonomi, Andrea Vitaletti

Vedi anche: Prof. Nicola Galesi · Computational Complexity a Sapienza (tutti i canali)