Exemples de réduction polynomiale
Il y a plein de choix possibles sur les réductions à faire…
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 26 | Classes P et NP. Problèmes NP-complets. Exemples.2022 |
| 4 | 915 | Classes de complexité. Exemples.2021 |
Utilisateur : Meven
3-SAT $\leq_P$ CLIQUE et 3-SAT $\leq_P$ SUBSET-SUM
Références :
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest