Computability and Complexity Theory

Course Code
υπο-πολ
ECTS Credits
5
Semester
5th Semester
Course Category

Specialization courses

Specialization courses

Specialization
Specialization elective courses on Informatics
Course Description
COURSE CONTENTS

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

Assessment: Written exams at the end of the semester.