Réduction polynomiale
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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 (En logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème de la logique égalitaire du premier ordre,...) et son langage associé

Codage (De façon générale un codage permet de passer d'une représentation des données vers une autre.)

Soit Q\! un problème de décision. Les instances de ce problème sont des objets abstraits au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution...) où leur définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) est purement mathématique. Pour permettre l'implémentation (Le mot implantation peut avoir plusieurs significations :) 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) des instances abstraites de Q\! un élément de \left\{0,1\right\}^*. Ainsi, lorsqu'un programmeur (En informatique, un développeur (ou programmeur) est un informaticien qui réalise du logiciel en créant des algorithmes et en les mettant en œuvre dans un langage de programmation.) 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 (En informatique, un interprète (parfois appelé, à tort, « interpréteur » par mauvaise traduction de l'anglais) est un outil ayant pour tâche d'analyser, de traduire et d'exécuter un programme écrit dans un langage informatique. De...) dans le cas des langages dynamiques) en langage binaire. Le codage est donc un moyen de passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) 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 (Le mot chaîne peut avoir plusieurs significations :) 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é (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la calculabilité qui s'attache à savoir si un...) et langage

On peut, de manière informelle définir une classe de complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en informatique ou en...) 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 (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un événement, etc.) 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 (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) polynomial.

Utilité

La notion de réduction en temps polynomial est utilisée dans le cadre de la théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la...) 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 ( En théorie des graphes, dans les ouvrages de référence, une clique est un ensemble de sommets deux-à-deux adjacents. Dans les armées, une clique désigne également une fanfare ou une musique militaire....) vers 3-sat
  • Sat vers 3-sat
  • Subset-sum vers sat
  • 3-sat vers clique
  • 3-sat vers vertex cover
Page générée en 0.062 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique