Reduction polynomiale

Reduction polynomiale

Réduction polynomiale

Sommaire

Définition

Dans le cadre des langages formels pour les problèmes de décision, on dit qu'un langage L_1\! est réductible en temps polynomial à un langage L_2\! (noté L_1 \le_P L_2) s'il existe une fonction calculable en temps polynomial f : \left\{0,1\right\}^* \rightarrow \left\{0,1\right\}^* telle que pour tout x \in \left\{0,1\right\}^*, x \in L_1 si et seulement si f(x) \in L_2. On appelle la fonction f\! la fonction de réduction, et un algorithme polynomial qui calcule f\! est appelé algorithme de réduction.

Relation entre un problème de décision et son langage associé

Codage

Soit Q\! 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 c\! d'un problème de décision Q\! comme étant une application injective qui associe à l'ensemble des instances abstraites de Q\! un élément de \left\{0,1\right\}^*. 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 i \in I est Q(i) \in \left\{0,1\right\}, alors la solution de l'instance du problème concret c(i) \in \left\{0,1\right\}^* est aussi Q(i)\!. Un léger problème se pose cependant : il est possible que des éléments de \left\{0,1\right\}^* 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

  • Un algorithme A\! accepte une chaîne x \in \left\{0,1\right\}^* si, étant donné une entrée x\!, l'algorithme sort  A(x) = 1\!
  • Un algorithme A\! rejette une chaîne x\! si A(x) = 0\!.

Langage accepté

  • Le langage accepté par un algorithme A\! est l'ensemble des chaînes acceptées par l'algorithme, soit L = \left\{ x \in \left\{0, 1\right\}^* : A(x) = 1\right\}.

Langage décidé

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

Classe de complexité et langage

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 x\! appartient au langage L\!. Ainsi la classe de complexité P\! peut-être définie comme étant l'ensemble des langages sur \left\{0,1\right\}^* qui sont décidés par un algorithme en temps polynomial.

Utilité

La notion de réduction en temps polynomial est utilisée dans le cadre de la théorie de la complexité 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 L_1 \le_P L_2 alors L_1\! n'est pas plus difficile que L_2\!, ou dit de manière plus théorique : L_1\! et L_2\! ont la même classe de complexité.

Exemples de réduction

  • Couvert vers subset-sum
  • Clique vers 3-SAT
  • SAT vers 3-SAT
  • Subset-sum vers SAT
  • 3-SAT vers clique
  • 3-SAT vers vertex cover
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « R%C3%A9duction polynomiale ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Reduction polynomiale de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Réduction polynomiale — Sommaire 1 Définition 2 Relation entre un problème de décision et son langage associé 2.1 Codage 2.2 R …   Wikipédia en Français

  • Reduction d'endomorphisme — Réduction d endomorphisme En mathématiques, et plus particulièrement en algèbre linéaire, la réduction d endomorphisme est une technique mathématique qui a pour objectif d exprimer des matrices et des endomorphismes sous une forme plus simple,… …   Wikipédia en Français

  • Réduction d'endomorphismes — Réduction d endomorphisme En mathématiques, et plus particulièrement en algèbre linéaire, la réduction d endomorphisme est une technique mathématique qui a pour objectif d exprimer des matrices et des endomorphismes sous une forme plus simple,… …   Wikipédia en Français

  • Réduction des endomorphismes — Réduction d endomorphisme En mathématiques, et plus particulièrement en algèbre linéaire, la réduction d endomorphisme est une technique mathématique qui a pour objectif d exprimer des matrices et des endomorphismes sous une forme plus simple,… …   Wikipédia en Français

  • Réduction d'endomorphisme — En mathématiques, et plus particulièrement en algèbre linéaire, la réduction d endomorphisme est une technique mathématique qui a pour objectif d exprimer des matrices et des endomorphismes sous une forme plus simple, notamment pour faciliter les …   Wikipédia en Français

  • Théorie de la complexité des algorithmes — Pour les articles homonymes, voir Théorie de la complexité. La théorie de la complexité des algorithmes étudie formellement la quantité de ressources (en temps et en espace) nécessitée par l exécution d un algorithme ainsi que la difficulté… …   Wikipédia en Français

  • Classe NP — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Classe de complexité — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Classes de complexité P et NP — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Complexite P — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”