Complexity Theory

ECTS : 3

Volume horaire : 15

Description du contenu de l'enseignement :

The topic of the course is the fundamentals of computational complexity. Once we have an algorithm for a problem, a question that always poses itself is whether an even better algorithm exists. In this course we will see some of the basic tools of computational complexity theory which allow us to show that certain algorithms cannot be improved. For this, we will discuss complexity classes (including the famous P=NP question), reductions between problems, and prove the basic relations between different classes of complexity.

Compétence à acquérir :

• Learn how to show that a problem does not admit an efficient algorithm
• Learn to recognize different classes of complexity with respect to time and space usage
• Learn the basic relations between deterministic and non-deterministic complexity classes

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.