TrainingsMasterInformatiqueCoursesComplexity and computability

Master InformatiqueUE Complexity and computability


When we define neatly and consider the set of « algorithms » (Turing machines) and the set of « things an algorithm may compute » (functions), we can notice, thanks to an argument from the 19th century (Cantor's diagonal), that there are strictly more « things to compute » than « algorithms to compute them ». Then what are these things a computer cannot compute ?

This course will teach the basics of computational complexity and answer to the following questions : within the set of computable things, how to define the hardness of a « thing to compute » (aka problem) ? When defined neatly (again some maths), these questions raise fundamental open problems of our century, such as the famous 1,000,000 usd question mark : does P equal NP ?

You will also be given the tools to say : « this problem is reasonably solvable on a computer » (in P) or « this one is not » (NP-hard).

Language used

Main language used by this course: Anglais.

Volume of teachings

  • Lectures: 12 hours
  • Tutorials: 12 hours
  • Pratical works: 12 hours



The trainings which use this course