Réduction (complexité)

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 (i.e. plus difficile ou 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 A ≤ B.

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 A ≤ B avec ≤ une réduction en temps polynomial avec B appartenant à P assure que A est aussi dans P.

Exemple introductif

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 C ≤ M. Mais l'autre inégalité (M ≤ C) est vraie aussi, grâce à la formule :

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

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
• Les réductions de Levin sont des fonctions polynomiales, qui en plusieurs transforment les certificats
• 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. 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é.

Voir aussi

Gadget