Réduction polynomiale

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques image illustrant l’informatique théorique
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Consultez la liste des tâches à accomplir en page de discussion.

Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Cet article ne cite pas suffisamment ses sources (novembre 2012).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » (modifier l'article, comment ajouter mes sources ?).

Une réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité. C'est une classe particulière de réductions particulièrement importante, notamment pour le problème P = NP.

Définition[modifier | modifier le code]

Dans le cadre des langages formels pour les problèmes de décision, on dit qu'un langage est réductible en temps polynomial à un langage (noté ) s'il existe une fonction calculable en temps polynomial telle que pour tout , si et seulement si . On appelle la fonction la fonction de réduction, et un algorithme polynomial qui calcule est appelé algorithme de réduction.

Relation entre un problème de décision et son langage associé[modifier | modifier le code]

Codage[modifier | modifier le code]

Soit un problème de décision. Les instances de ce problème sont des objets abstraits au sens où leur définition est purement mathématique. Pour permettre l'implémentation de ce problème, elles doivent être cependant représentées sous une forme compréhensible par le programme. Ici intervient la notion de codage. On définit une fonction de codage d'un problème de décision comme étant une application injective qui associe à l'ensemble des instances abstraites de un élément de . Ainsi, lorsqu'un programmeur code un problème, les variables représentant les instances du problème sont traduites (par le compilateur dans le cas des langages statiques, par l'interpréteur dans le cas des langages dynamiques) en langage binaire. Le codage est donc un moyen de passer d'un problème abstrait à un problème concret. De fait, si la solution à une instance de problème de décision abstrait est , alors la solution de l'instance du problème concret est aussi . Un léger problème se pose cependant : il est possible que des éléments de ne correspondent à aucune instance du problème (autrement dit, qu'ils n'ont aucun antécédent). Par commodité, on supposera que toute chaîne de ce type a pour image 0.

Relation entre les problèmes de décisions et les algorithmes qui les résolvent[modifier | modifier le code]

  • Un algorithme accepte une chaîne si, étant donné une entrée , l'algorithme sort
  • Un algorithme rejette une chaîne si .

Langage accepté[modifier | modifier le code]

  • Le langage accepté par un algorithme est l'ensemble des chaînes acceptées par l'algorithme, soit .

Langage décidé[modifier | modifier le code]

  • Un langage est décidé par un algorithme si toute chaîne binaire n'appartenant pas à est rejetée par .

Classe de complexité et langage[modifier | modifier le code]

On peut, de manière informelle définir une classe de complexité comme un ensemble de langages dont l'appartenance est déterminée par une mesure de la complexité d'un algorithme qui détermine si une chaîne donnée appartient au langage . Ainsi la classe de complexité peut-être définie comme étant l'ensemble des langages sur qui sont décidés par un algorithme en temps polynomial.

Utilité[modifier | modifier le code]

La notion de réduction en temps polynomial est utilisée dans le cadre de la théorie de la complexité des algorithmes pour permettre la classification des problèmes. Elle permet en effet de montrer de manière formelle, et en un temps polynomial, qu'un problème est au moins aussi difficile qu'un autre : si alors n'est pas plus difficile que , ou dit de manière plus théorique : et ont la même classe de complexité.

Exemples de réduction[modifier | modifier le code]

Notes et références[modifier | modifier le code]