====== Theory of Complexity ======
----
===== News =====
<WRAP center round important 95%>
  * <wrap em>**September 7th, 2016**</wrap>: the course web site is now on-line
</WRAP>

----
===== General Info =====
<WRAP box round 95% center>
**Teacher**: 
  * [[http://docenti.unicam.it/pdett.aspx?ids=N&tv=d&UteId=196&ru=PO|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
</WRAP>
----
===== Course Objectives =====

<WRAP box round 95% center>
D1 - CONOSCENZA E CAPACITÀ DI COMPRENSIONE
Risultati attesi:
Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:
  - illustrare la tesi di Church e Turing e l’esistenza (modulo questa assunzione) di problemi insolubili in Informatica e Matematica,
  - valutare il costo delle computazioni e la complessità degli algoritmi e descrivere i parametri atti a misurarli,
  - riconoscere problemi informatici e matematici risolubili a costi accessibili, oppure risolubili solo a costi inaccessibili,
  - discutere il ruolo delle classi P e NP, del problema P = NP e dei linguaggi NP-completi,
  - 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:
  - valutare in semplici casi l’efficienza di un algoritmo,
  - identificare input e output di un algoritmo,
  - 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:
  - 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:
  - esporre in modo ordinato e coerente una procedura.

D5 - CAPACITÀ DI APPRENDIMENTO
</WRAP>

----
===== Course Contents =====

<WRAP round 95% center box>
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.
</WRAP>
----
===== Study material =====
<WRAP box round center 95%>
**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
</WRAP>
----
===== Exams =====
<WRAP box round center 95%>
**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 [[http://docenti.unicam.it/pdett.aspx?ids=N&tv=d&UteId=196&ru=PO|portale docenti]].

** Exam Results **
  * N/A
</WRAP>