Computability and Complexity Theory

Lecture and tutorial classes in the summer term

This will be a standard course on computability and complexity theory. Large parts will be based on the book "Introduction To The Theory Of Computation" by Michael Sipser.

Topics

  • Basic models of computation (finite state machines, Turing machines)
  • Decision problems and formal languages
  • Gödel numbering of computations
  • Universal computability
  • Decidable and undecidable problems
  • Reductions, diagonalization
  • Time and space complexity
  • The complexity classes P and NP
  • Hierarchy theorems
  • Polynomial time reductions, NP-completeness
  • Cook-Levin theorem
  • Uniform circuit families

Nach oben