Computational Complexity, 2nd cuatrimestre 2025
Undergraduate course, Universidad de Buenos Aires, FCEyN, Departmento de Computación, 2025
Since march until july, and 2 hs of theory and 3 hs of practical exercises, the topics were:
- Turing machine (deterministic and non-deterministic)
- Computing time
- Polynomial time:
- P class
- NP class
- Polynomial reduction and NP-complete problems
- Cook-Levin theorem
- The co-NP class
- The ExpTime and NExpTime
- Separation of complexity class
- Deterministic time hierarchies
- Non-deterministic time hierarchies
- Leadner theorem
- Space used by a computation
- Polynomial space: PSpace and NPSpace
- Savitch theorem
- Logarithmic space: L and NL
- Immerman-Szelepcsényi theorem
- Polynomial hierarchy
- \(\Sigma_i^p\)-complete problems
- Oracle machines
- Bacher-Gill-Solovay theorem
- Boolean circuits
- The P\(_{/poly}\) class
- Karp-Lipton theorem
- NC and AC classes
- P-completeness

Leave a Comment
Your email address will not be published. Required fields are marked *