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 *

Loading...