Chapitre 10 / 12
Problèmes NP-complets
Certificats, réductions et SAT
Le cours présente NP, les transformations polynomiales, SAT, le théorème de Cook et l’exemple du Sudoku.
💡 À retenir : Ne pas confondre NP avec « non polynomial » : NP concerne la vérification polynomiale des certificats.
🧩 Vérification d’une formule SAT
Exemple pédagogique complémentaire : F = (A ∨ B) ∧ (¬A ∨ C). Testez une affectation des variables.