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