Réduction (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Réduction.

En calculabilité et en théorie de la complexité, une réduction est un algorithme transformant un problème en un autre.

Cet outil sert à montrer qu'un problème est au moins aussi difficile qu'un autre : si un problème A peut être réduit à (i.e. transformé en) un problème B, et que le problème A est difficile alors le problème B est au moins aussi difficile. On écrit alors AB.

Les réductions permettent entre autres de prouver que des problèmes sont indécidables ou bien sont complets pour une certaine classe de complexité. Dans certains cas, une réduction peut aussi permettre de montrer qu'un problème est facile, par exemple AB avec ≤ une réduction en temps polynomial avec B appartenant à P assure que A est aussi dans P[1].

Exemple introductif[modifier | modifier le code]

Supposons que l'on veuille faire des calculs sur les entiers et que l'addition, la soustraction et la division soient des opérations autorisées. On veut savoir si faire une multiplication (problème M) est plus ou moins difficile que d'élever un nombre au carré (problème C). Un sens est facile : si l'on sait faire une multiplication, on peut élever un nombre au carré en le multipliant par lui-même, donc CM. Mais l'autre inégalité (MC') est vrai aussi, grâce à la formule :

a \times b = \frac{\left(\left(a + b\right)^{2} - a^{2} - b^{2}\right)}{2}

Les deux problèmes sont aussi difficiles l'un que l'autre (ils peuvent être réduits l'un à l'autre).

Définitions[modifier | modifier le code]

Les définitions qui suivent mettent en jeu des entiers car les instances des problèmes sont codées dans ℕ.

Etant donnés deux ensembles d'entiers naturels A et B, et un ensemble de fonctions F de ℕ dans ℕ, clos par composition, A est dit réductible à B par F si : \exists f \in F \mbox{ . } \forall x \in \mathbb{N} \mbox{ . } x \in A \Leftrightarrow f(x) \in B

On écrit : A \leq_{F} B.

Soit S un sous-ensemble de P(ℕ) et ≤ une réduction, alors S est dit clos par ≤, si \forall s \in S \mbox{ . } \forall A \in P(N) \mbox{ . } A \leq s \Rightarrow A \in S

Un sous-ensemble A de ℕ est dit difficile pour S, si \forall s \in S \mbox{ . } s \leq A

Enfin un sous-ensemble A de N est dit complet pour S, si A est difficile pour S et A appartient à S.

Exemples[modifier | modifier le code]

Pour prouver qu'un problème est NP-complet, on peut réduire un problème NP-complet connu (comme le problème SAT) à ce problème, à l'aide d'une réduction polynomiale.

Dans le domaine de la calculabilité, on peut par exemple prouver le théorème de Rice par réduction du problème de l'arrêt.

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

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l’algorithmique, Dunod,‎ 2002, 2e éd., 1146 p. [détail de l’édition] (ISBN 2-10-003922-9) chap 34, NP-completude