Theory of Complexity

Teacher:

• Carlo Toffalori

Lessons schedule:

• Monday, 11am - 1pm
• Tuesday, 5pm - 7pm

Students Office hours:

• Contact the teacher by phone or e-mail to fix an appointment

D1 - CONOSCENZA E CAPACITÀ DI COMPRENSIONE Risultati attesi: Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

1. illustrare la tesi di Church e Turing e l’esistenza (modulo questa assunzione) di problemi insolubili in Informatica e Matematica,
2. valutare il costo delle computazioni e la complessità degli algoritmi e descrivere i parametri atti a misurarli,
3. riconoscere problemi informatici e matematici risolubili a costi accessibili, oppure risolubili solo a costi inaccessibili,
4. discutere il ruolo delle classi P e NP, del problema P = NP e dei linguaggi NP-completi,
5. illustrare le altre classi principali dello zoo della complessità.

D2 - CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE Risultati attesi: Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

1. valutare in semplici casi l’efficienza di un algoritmo,
2. identificare input e output di un algoritmo,
3. descrivere un algoritmo di soluzione, distinguendo i passi successivi del suo sviluppo.

D3 - AUTONOMIA DI GIUDIZIO Risultati attesi: Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

1. distinguere input e output di un’istanza di un problema e i passi successivi di un algoritmo che conduce dall’uno all’altro,

D4 - ABILITÀ COMUNICATIVE Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

1. esporre in modo ordinato e coerente una procedura.

D5 - CAPACITÀ DI APPRENDIMENTO

Verso una definizione astratta del concetto di algoritmo. Macchine di Turing. Tesi di Church e Turing. Cenni sul problema dell’arresto, sul decimo problema di Hilbert e su altri problemi insolubili in matematica e in informatica.
Il problema della complessità. Complessità di una macchina di Turing.
Il parametro tempo: la tesi di Cook-Karp, le classi P e NP, il problema P=NP. Linguaggi NP-completi. Teorema di Cook-Levin. Linguaggi NP-intermedi. La gerarchia polinomiale.
Il parametro spazio: le classi L, NL, PSPACE. Teorema di Savitch. Linguaggi NL-completi. Linguaggi PSPACE-completi. Teorema di Baker-Gill-Solovay.
Complessità probabilistica: le classi PP, BPP, RP e ZPP.
Complessità interattiva: le classi AM, MA, AM[Poly] e IP. Cenni sul teorema di Shamir.
Cenni su complessità e circuiti.

Course Slides

• slide 1st lesson

Reference books

• F. Corradini-S. Leonesi-S. Mancini-C. Toffalori, Teoria della Computabilità e della Complessità, McGraw-Hill Italia, 2005

Exam Dates A.Y. 2016/2017

Exam rules:

Il raggiungimento dei risultati di apprendimento D1, D2, D3 e D4 sarà verificato attraverso una prova orale finale con semplici esercizi e da discussioni durante il corso. Altre informazioni potranno essere reperite nello spazio web del docente sul portale docenti.

Exam Results

• N/A