Polynomial Reduction
Une réduction polynomiale convertit le problème A en problème B en temps polynomial ; si B est résoluble alors A l’est aussi, ce qui sert à prouver la NP-dureté.
Objectif
Prouver la dureté des problèmes et transférer la résolubilité ; un outil central de la théorie de la complexité.
Mécanisme
A ≤_p B : il existe une fonction f en temps polynomial qui mappe les instances de A vers les instances de B telle que A(x)=B(f(x)). Si B∈P alors A∈P. Si A est connu comme NP-difficile et A≤_p B, alors B est NP-difficile.
Cas d’usage
- Preuves de complexité
- Réductions NP-difficiles
- Classification des problèmes