Course contents: Problems as languages (decision vs search problems). Finite automata. Models of computation – Turing Machines and variants of TMs. Decidable and Undecidable Problems, Recursively Enumerable Languages and beyond. Complexity classes and known relations, hierarchy theorems. The class NP, NP-complete problems, Cook and Karp reductions. PSPACE completeness, Polynomial Hierarchy. 
Time permitting, a quick review on the structural aspects and the inherent difficulties of the P vs NP problem up to the Baker-Gill-Solovay Theorem. Alternatively, a quick view of approximability of NP-hard problems.

Assessment: Written exams at the end of the semester.