Sillabo dell'insegnamento

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