Problèmes industriels et réduction polynomiale 101

Réduction polynomiale

Les problèmes de la recherche opérationnelle, et plus généralement de l’aide à la décision sont souvent Np-complet, c’est-à-dire que l’on ne connaît pas d’algorithmes permettant de trouver une solution optimale en temps polynomial, mais on sait obtenir une solution réalisable en temps polynomiale (par réduction polynomiale).

Complexité polynomiale

Un algorithme est de complexité polynomiale s’il existe un polynôme P tel que le nombre d’instructions élémentaires effectuées lors de son exécution sur une instance de taille n soit au plus P(n). Un problème est de complexité polynomiale s’il existe un algorithme de complexité polynomiale le résolvant. Il est important de souligner que la représentation des structures de données utilisées n’influe pas la complexité.

Réduction polynomiale

Un problème de décision P se réduit à un problème de décision P’ s’il existe un algorithme polynomial R qui transforme toute entrée u de P en une entrée u’=R(u) de P’ telle que u∈Oui(P) ⇔ u’∈Oui(P’).

Cela suggère l’implication suivante : s’il existe un algorithme polynomial pour P’, alors il en existe aussi un pour P.