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


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