Sillabo dell'insegnamento

• A - Fondamenti
* CAL - Calcolabilita'
Recall of Basic Computability Theory. The cost of computing. How to measure it: time, space, energy, other parameters. Complexity of a computation. Feasible problems.
COM - Complessita'
Time: the class P, the thesis od Edmond-Cook-Karp, the class NP, the question P=NP, NP-complete problems, SAT, the Cook-Levin Theorem. NP-intermediate problems. The polynomial hierarchy.
COM - Complessita'
Space: the classes L, NL, PSPACE. NL-complete problems and PSPACE-complete problems, QSAT. The Savitch Theorem. Oracles and the Baker-Gill-Solovay theorem.
COM - Complessita'
Probabilistic procedures. The classes BPP, RP and ZPP. ZPP as the class of problems solvable in average polynomial time.
COM - Complessita'
Interactive procedures. Arthur and Merlin. AM and MA. The class IP. Shamir's Theorem. The complexity zoo.
COM - Complessita'
Complexity and circuits. Logical gates. The problem of unique satisfiability.