Ects : 3

Enseignant responsable :

• MICHAIL LAMPIS

Volume horaire : 15

Description du contenu de l'enseignement :

In this course we study the basics of computational complexity theory, focusing on time complexity, space complexity, and non-determinism. We discuss standard complexity classes, including P, NP, coNP, PSPACE, and the relations between them. We will explain how the notion of reductions allows us to understand the relative difficulty of two problems, even when both problems are intractable and see how reductions lead to the notion of problems complete for a class. We also study the fundamental notion of NP-completeness and its relatives (such as PSPACE-completeness) and explain what this notion means for computer science in general. If time allows we will also discuss more advanced complexity classes, such as the polynomial hierarchy, the boolean hierarchy, and randomized complexity classes.

Compétence à acquérir :

In the end of this course students will have learned how one can prove that a problem is intractable, what it means for a problem to be NP-complete or complete for another class, and the most important classes of computational complexity.

Bibliographie, lectures recommandées

Bibliography

S. Arora, B. Barak, Computational Complexity. A modern approach, Cambridge University Press, 2009.

M.R Garey, D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W. H. Freeman, 1979.

C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.