Aller au contenu principal

Complexité des problèmes

Progression

#Complexité des problèmes : classes et NP-complétude

Le module élargit ensuite le point de vue en s’intéressant aux classes de problèmes : P, NP, co-NP, EXP. Nous définissons rigoureusement chacune d’elles avant de montrer comment les réductions polynomiales relient les problèmes entre eux. SAT, 3-SAT, CLIQUE ou couverture minimale servent de jalons pour comprendre ce que signifie la NP‑complétude et pourquoi le théorème de Cook-Levin est fondateur.

Pour ancrer ces notions dans la pratique, nous adoptons une perspective d’ingénierie. Quand faut-il accepter une solution approchée ? quelles heuristiques (tabou, recuit simulé, branch and bound) peuvent être mises en place pour obtenir rapidement des solutions satisfaisantes ? Enfin, nous parlons certification : soit prouver l’optimalité, soit produire un certificat que l’on peut vérifier efficacement pour des problèmes NP.

#Exercices

  1. Réduisez Vertex Cover à Set Cover.
  2. Implémentez un solveur SAT naïf et observez sa croissance empirique.