NP-Completeness
Un problème NP-complet appartient à NP et tout problème de NP se réduit à lui en temps polynomial ; ce sont les problèmes les plus difficiles de NP.
Objectif
Comprendre la hiérarchie de complexité et reconnaître les problèmes intraitables.
Mécanisme
NP : vérifiable en temps polynomial. NP-difficile : tout problème de NP se réduit à lui. NPC=NP∩NP-difficile. Si un problème NPC admettait une solution polynomiale, alors P=NP. Classiques : SAT, TSP, couverture par sommets.
Cas d’usage
- Analyse de complexité
- Évaluation de la difficulté des problèmes
- Preuves par réduction