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.

Outline

• Turing machines as basic model of computation
• Different TM variants and equivalence (multi-tape TMs, non-deterministic TMs, enumerators)
• Church Turing thesis
• Encodings of objects such as TMs
• Dedcidablity of acceptance, emptyness, and equivlence problems for DFAs, CFGs, LBAs, and TMs
• Diagonalization
• Mapping recucibility
• Computation history method and the Post correspondence problem
• Time complexity, model dependence, class P, example graph problems in P 
• Class NP (2 definitions + equivalence)
• Karp reductions, NP-completeness
• Problems: Hamiltonian path, k-clique, SAT, 3SAT
• 3SAT, HAMPATH, CLIQUE
• Cook-Levin theorem
• Probabilistic TMs, class BPP
• Read once branching programs (ROBPs)
• Arithmetization, checking equivalence of ROBPs is in BPP
• Space complexity and basic classes
• True quantified Boolean formulae are PSPACE-complete
• NPSPACE and proof idea of Savitch’s theorem
• Generalized geography is PSPACE-complete