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