Pour les articles homonymes, voir Réduction.

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 appartient à P, alors A est aussi dans P^[1].

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 ${\displaystyle 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 :

${\displaystyle 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).

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 : ${\displaystyle \exists f\in F{\mbox{ . }}\forall x\in \mathbb {N} {\mbox{ . }}x\in A\Leftrightarrow f(x)\in B}$

On écrit : ${\displaystyle A\leq _{F}B}$.

Soit S un sous-ensemble de P(ℕ) et ≤ une réduction, alors S est dit clos par ≤, si ${\displaystyle \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 ${\displaystyle \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.

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.

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]

Gadget

• Portail de l'informatique théorique