MA5011 - Complexity

MA5011 - Complexity


General objective:

Understand and be able to compute the complexity of sequential algorithms.
Recognize combinatorial problems and be able to prove their hardness.
Apprehend cryptographic systems.

Detailed objectives:

Understand the different notions of the complexity of an algorithm and be able to analyze non-recursive
and recursive sequential algorithms.
Understand the complexity of decision problems and the underlying non-deterministic Turing machine
computation model.
Master Turing reduction between problems and classes P, NP and NPC.
Recognize and prove the NP completeness or hardness of combinatorial optimization problems.
Understand how complex problems can be used to create asymmetric cryptosystems.


  • Lectures : 20

Form of assessment

Total assessment hours: 3

In brief

ECTS credits : cf Teaching Unit

Number of hours 23



Phone : +33 5 62 25 95 06

Email : nicolas.barnier @

Jean-Baptiste GOTTELAND

Phone : +33 5 62 25 95 84

Email : jean-baptiste.gotteland @