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.

Contacts

Head of Master MODO: Daniel VANDERPOOTEN

Secretariat :
  Office :B530
  Tel. : +33 1 44 05 42 47
  email : master-modo@dauphine.fr

Address:
  Université Paris Dauphine
  Master MODO - Bureau P619
  Place du Maréchal de Lattre de Tassigny
  75775 Paris Cedex 16, France