Complexity Theory

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.