Objectives: The course is about complexity of algorithms fundamentals. It mainly handles intractability, reducibility, and notions of completeness/hardness for complexity classes.
Contents:
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
Bibliography
R. G. Downey, M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.
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.
V. Th. Paschos, Complexité et Approximation Polynomiale, Hermès, 2004.