Basic Complexity Classes

NP and NP-completeness

Diagonalization

Space Complexity

Boolean Circuits

Polynomial Hierarchy

Barriers Results

Intro To Proof Complexity

- Theoretical model of resource running time
- Theoretical model ofresource memory occupation
- Time and Space complexity classes
- The P = NP problem
- Unfeasible problems when resources are bounded
- Computational Classes L, P, NP, PSPACE, BPP, #P, IP,
- Main Results