Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
Probabilistic Proof Systems: Interactive Proof Systems, The Power of Interactive Proofs, Zero-Knowledge Proof Systems.
COM - Complessita'
Randomness and Counting: Probabilistic Polynomial-Time, Two-sided error and One-sided error.
COM - Complessita'
The Bright Side of Hardness: One-Way Functions, Pseudorandom Generators, Computational Indistinguishability.
COM - Complessita'
Space Complexity: Time versus Space, Logarithmic Space, PSPACE and Games.
COM - Complessita'
Introduction and Preliminaries; Computational Tasks; Uniform Models (Turing machines, Time and space complexity, Oracle machines]; Complexity Classes.
COM - Complessita'
P, NP and NP-Completeness; The search version - finding versus checking; The decision version - proving versus verifying; Polynomial-time Reductions; NP-Completeness.