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[modifier | modifier le code]

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[modifier | modifier le code]

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[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.

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

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[modifier | modifier le code]

Gadget

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

↑ 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]

v · m Sécurité prouvable en cryptologie
Modèles de sécurité	Modèle standard Modèle de l'oracle aléatoire (ROM) Modèle du groupe générique (GGM) Modèle du groupe algébrique (AGM) Modèle du chiffre idéal (ICM) Modèle de l'action de groupe à sens unique (OWGA) Transfert inconscient (OT) Fonction à perte extrême (ELF) Fonction pseudo-aléatoire (PRF) Permutation pseudo-aléatoire (PRP) Générateur pseudo-aléatoire (PRG) Groupe bilinéaire Application multilinéaire Modèle de la chaîne de référence commune (CRS) Fonction à sens unique (OWF) Fonction à trappe (TDF) Obfuscation indistinguable (iO) Composabilité universelle (UC)
Outils et techniques de preuve	Réduction Séparation Avantage Argument hybride Distance statistique Coefficient H Simulation Forking lemma Leftover hash lemma Lemme de Schwartz-Zippel Théorème de Luby-Rackoff Théorème des anniversaires Heuristique de Fiat-Shamir
Hypothèses calculatoires	Factorisation Problème RSA Problème RSA fort Problème du logarithme discret Problème de Diffie-Hellman (CDH et DDH) Problème de la résiduosité quadratique Problème de la résiduosité supérieure Navigation dans un graphe expanseur Problème LWE Problème NTRU Problèmes de réseau (SVP, CVP, SIS, SIVP)
Propriétés de sécurité	IND (indistingabilité) EF (forge existentielle) NM (non malléabilité) Résistance aux collisions (CR) CPR (résistance aux collisions à préfixe choisi) PIR (résistance aux préimages) SPIR (résistance aux secondes préimages) Divulgation nulle de connaissance (ZK)
Modèles d'attaques	Attaque sans message (NMA) Clairs/messages choisis (CPA/CMA) Chiffrés choisis (CCA) Chiffrés choisis de façon adaptative (CCA2) Attaque par sondes (ISW)