Réduction (complexité)

En calculabilité et en théorie de la complexité, une réduction est un algorithme transformant une instance d'un problème algorithmique en une ou plusieurs instances d'un autre problème. S'il existe une telle réduction d'un problème A à un problème B, on dit que le problème A se réduit au problème B. Dans ce cas, le problème B est plus difficile que le problème A, puisque l'on peut résoudre le problème A en appliquant la réduction puis un algorithme pour le problème B. On écrit alors A ≤ B.

Il y a deux utilisations des réductions.

Montrer qu'un problème est intrinsèquement difficile. Par exemple, on utilise une réduction pour montrer que des problèmes sont indécidables : on montre alors que le problème est tellement algorithmiquement difficile, qu'il n'y a pas d'algorithmique qui le décide. Les réductions polynomiales sont utilisées pour démontrer que des problèmes sont NP-difficiles. Plus généralement, on démontre avec des réductions qu'un problème est parmi les plus difficiles d'une classe de complexité.
Montrer qu'un problème est facile à résoudre algorithmiquement. Par exemple, si A ≤ B avec ≤ une réduction en temps polynomial, et que B appartenant à P, alors A est aussi dans P^[1].

Exemple introductif

Considérons deux problèmes : le problème M de la multiplication de deux entiers, et le problème C de l'élévation au carré d'un entier. Le problème C est plus facile que le problème M. En effet, si l'on sait faire une multiplication, on peut élever un nombre au carré en le multipliant par lui-même, donc C ≤ M. La réduction de C dans M est $x\mapsto (x,x)$ : on transforme un entier à élever au carré en la donnée de deux entiers égaux (x, x) à multiplier.

De manière intéressante, on peut aussi démontrer que M se réduit à C (M ≤ C). En effet, grâce à la formule :

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

on voit que l'on peut calculer le produit de a et b, en calculant trois élévations au carré. Ainsi, les deux problèmes sont aussi difficiles l'un que l'autre (ils peuvent être réduits l'un à l'autre).

Définitions

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

Étant 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

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.

Types de réduction

Il existe plusieurs types de réduction.

Réduction de Turing
Réduction de Cook
Réduction en temps polynomial
Réduction en espace logarithmique
Réduction du premier ordre^[2]
Les réductions de Levin sont des fonctions polynomiales, qui en plusieurs transforment les certificats^[3]
Réduction en temps polynomial par table de vérité : un problème A se réduit en temps polynomial par table de vérité si on peut décider si x appartient à A, en précalculant plusieurs questions d'appartenance de mots à B et décrire une formule booléenne sur les réponses à ses questions pour décider l'appartenance de x à A^[4]. Plus précisément, Buss et Hay introduisent des variantes selon que la formule booléenne est représenté par son arbre syntaxique, un circuit ou la table de vérité^[5].
Réductions qui préservent le facteur d'approximation entre problème d'optimisation, dans le domaine des algorithmes d'approximation^[6]

Voir aussi

Gadget

Notes et références

↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition] chap 34, NP-completude
↑ (en) Immerman, Descriptive complexity
↑ (en) Arora, Barak, Computational complexity - A modern approach, p. 55
↑ (en) « A comparison of polynomial time reducibilities », Theoretical Computer Science, vol. 1, n^o 2,‎ 1^er décembre 1975, p. 103–123 (ISSN 0304-3975, DOI 10.1016/0304-3975(75)90016-X, lire en ligne, consulté le 18 décembre 2018)
↑ Samuel R. Buss et Louise Hay, « On Truth-table Reducibility to SAT », Inf. Comput., vol. 91, n^o 1,‎ mars 1991, p. 86–102 (ISSN 0890-5401, DOI 10.1016/0890-5401(91)90075-D, lire en ligne, consulté le 18 décembre 2018)
↑ (en) Vijay V. Vazirani, Approximation Algorithms, Springer-Verlag, 2003 (ISBN 978-3-540-65367-7, lire en ligne), sectionA.3.1, p.348

Portail de l'informatique théorique

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition] chap 34, NP-completude

[2] (en) Immerman, Descriptive complexity

[3] (en) Arora, Barak, Computational complexity - A modern approach, p. 55

[4] (en) « A comparison of polynomial time reducibilities », Theoretical Computer Science, vol. 1, n^o 2,‎ 1^er décembre 1975, p. 103–123 (ISSN 0304-3975, DOI 10.1016/0304-3975(75)90016-X, lire en ligne, consulté le 18 décembre 2018)

[5] Samuel R. Buss et Louise Hay, « On Truth-table Reducibility to SAT », Inf. Comput., vol. 91, n^o 1,‎ mars 1991, p. 86–102 (ISSN 0890-5401, DOI 10.1016/0890-5401(91)90075-D, lire en ligne, consulté le 18 décembre 2018)

[6] (en) Vijay V. Vazirani, Approximation Algorithms, Springer-Verlag, 2003 (ISBN 978-3-540-65367-7, lire en ligne), sectionA.3.1, p.348

[1]

[2]

[3]

[4]

[5]

[6]