Dimitri Watel

COMPUTATIONAL COMPLEXITY

Other teacher(s) : Olivier Hudry

Official webpage

This course is shared by the students of the ENSIIE (Course OPTI1-ICA) and the MPRO (course TC). The computational complexity study the inherent difficulty of a problems. Particularly, it gives the time needed to solve them. This course is an introduction to the complexity classes and how to determine them, it is illustrated mostly with combinatorial and/or graph problems.
  1. Complexity of a decision problem
  2. Turing machines
  3. Complexity classes
  4. Reductions and completeness
  5. The Cook-Levin theorem
  6. Optimization problems
  7. Inputs encoding
  8. Other classifications

Tutorials

  1. Decision problems and Turing machines (Correction)
  2. Complexity classes (Correction)
  3. Reductions and completeness (Correction)
  4. Optimization problems (Correction)
  5. Inputs encoding (Correction)

Board annotations

More

Change language : Français English