Computational Complexity

DEPARTMENT OF MATHEMATICS

618 Computational Complexity (5ο semester)

Instructors: D. Thilikos. L. Kirousis

Models of computability, Turing machines, the notion of complexity of a problem. Complexity classes: Class PSPACE, Savitch's theorem, Classes Ρ and EXP. Non-Deterministic Turing machines. Classes NP and co-NP. The Projection Theorem. Reducibilities and Completeness, NP-hardness. Cook-Levin theorem, NP-complete problems, Methods of proof of NP-completeness, Pseudopolynomiality, Strongly NP-complete problems. NP-completness and approximability, EXP-complete and PSPACE-complete problems.

Textbooks:

Introduction of Theory Computation, Sipser Michael, Crete University Press http://www.cup.gr/ΕΙΣΑΓΩΓΗ-ΣΤΗ-ΘΕΩΡΙΑ-ΥΠΟΛΟΓΙΣΜΟΥ_p-264687.aspx?LangId=1

Element of the Theory Computation, Harry Lewis, Christos Papadimitriou, Kritiki Press http://www.kritiki.gr/lewis_papadimitriou