Complexity Theory

Ects : 3

Enseignant responsable :

Volume horaire : 15

Description du contenu de l'enseignement :

The course is about complexity of algorithms fundamentals. It mainly handles intractability, reducibility, and notions of completeness/hardness for complexity classes.

Compétence à acquérir :

  • Problems ’ intractability
  • Reductions and class inclusion preservation
  • Role of the parameters in the evaluation of a problem's complexity
  • Complexity classes wrt parameter “ size of instance ” : P, NP, co-NP, Karp and Turing reductions, NP-completeness
  • Complexity classes wrt parameter “ solution value ” , XP, FPT, W[ ]-hierachy, FPT reductions

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.