**1. Basic on Complexity Classes **

1.1 Theoretical models of computations and time and space resources

1.2 Time and space complexity classes

1.3 The P = NP problem

1.4 NP and NP-completeness

1.5 Unfeasible problems when resources are bounded

1.6 Computational Classes: L, NL, P, NP, PSPACE, BPP, RP, #P, IP,

1.7 Main Results

**2. Diagonalization**

**3. Hierarchies Theorems for time, space, deterministic and non deterministic computations **

**4. Barriers Results I: Diagonalization is not sufficient to prove P different from NP **

**5. Space Complexity **

5.1 Shamir Theorem: PSPACE = IP

5.2 Immerman-Szelepcsényi Theorem: NL=coNL,

**6. Boolean Circuits**

6.1 Basic definitions and efficient circuits

6.2 Bounded depth circuits: NC and AC hierarchies.

6.3 Hastad-Razborov-Smolensky Theorem: Parity requires exponential size bounded depth

circuits.

6.4 Monotone Circuits

**7. Polynomial Hierarchy and its basic theorems **

**8. Barriers Results - II [optional]**

8.1 Rudich-Razborov Theorem: "Natural proofs" are not sufficient to separate P from NP

(unless crypto fails)

**9. Other boolean models of computations and their computational limits: **

9.1 Decision trees

9.2 Branching programs.

**10. Introduction to Proof Complexity **

10.1. Logical proof systems: Resolution

10.2 Geometric proof systems: Chvatal's cuts

10.3 Algebraic proof system: Polynomial Calculus

10.4 Semialgebraic proof systems: Sherali-Adams and Sum-of-Squares

10.5 Exponential lower bounds for Resolution and Cutting planes: Ben-Sasson-Wigdeson width

method and Interpolation

- Teacher: Nicola Galesi