26 - Classes P et NP. Problèmes NP-complets. Exemples.2022

Rapport du jury 2019

L’objectif ne doit pas être de dresser un catalogue le plus exhaustif possible ; en revanche, pour chaque exemple, il est attendu que le candidat puisse au moins expliquer clairement le problème considéré, et indiquer de quel autre problème une réduction permet de prouver sa NP-complétude. $\\$ Les exemples de réduction polynomiale seront autant que possible choisis dans des domaines variés : graphes, arithmétique, logique, etc. Si les dessins sont les bienvenus lors du développement, le jury attend une définition claire et concise de la fonction associant, à toute instance du premier problème, une instance du second ainsi que la preuve rigoureuse que cette fonction permet la réduction choisie et que les candidats sachent préciser comment sont représentées les données. $\\$ Il peut être bienvenu de présenter un exemple de problème NP-complet dans sa généralité qui devient P si on contraint davantage les hypothèses, ou encore un algorithme P approximant un problème NP-complet.