Home
About

Réduction de problèmes

Cours/Algorithmie/Réduction de problèmes

Une méthode classique de résoudre un problème algorithmique ($P_1$) est de le transformer en un autre problème ($P_1$) que l'on sait résoudre ($S_2$) puis de transformer sa solution en une solution du problème initial ($S_1$) :

$$ \begin{array}{ccc} P_1 & \rightarrow & P_2\\ \Uparrow & & \Downarrow\\ S_1 & \leftarrow & S_2 \end{array} $$

La formalisation de cette opération s'appelle une réduction et peut prendre plusieurs formes. Nous en expliciterons certaines qui nous permettrons de :

  1. comparer et classer les problèmes algorithmiques.
  2. calculer ou estimer des complexité

Nous ne parlerons pas ici de la Réduction de Turing, trop générale et demandant des connaissances comme les machines à oracles dont nous ne parlerons pas dans ce cours d'algorithmie.

Commençons par un exemple :

Montrez que l'on peut :

  1. Transformer l'entrée $T$ d'un problème de la recherche du minimum dans un tableau d'entiers relatifs par une entrée $T'$ du problème de la recherche du maximum dans un tableau d'entiers relatifs,
  2. utiliser le maximum de $T'$ pour trouver le minimum de $T$.

Quelle est la complexité de cet algorithme en fonction de la complexité de l'algorithme utilisé pour rechercher le maximum dans un tableau d'entiers relatifs ?

corrigé

Le tableau $T'$ est tel que $T'[x] = -T[x]$ et on cherche $\max(T')$. Le min est alors : $\min(T) = -\max(T')$.

La complexité de passer de $T$ à $T'$ est $\mathcal{O}(n)$ avec $n$ la longueur de $T$ et comme $\min(T) = -\max(T')$, la complexité de passer d'une solution à l'autre est $\mathcal{O}(1)$. La complexité totale est alors en notant $C_{\min}(n)$ et $C_{\max}(n)$ la complexité des deux algorithme de résolution :

$$ C_{\min}(n) = \mathcal{O}(n) + C_{\max}(n) + \mathcal{O}(1) $$

Comme on a vu que la recherche du maximum d'un tableau est toujours au moins linéaire on en conclut que $C_{\min}(n) = C_{\max}(n)$

On peut même utiliser plusieurs fois l'algorithme $P_2$ :

Montrez que si l'on connaît un algorithme permettant de trouver le maximum dans un tableau d'entiers positifs on peut :

  1. Transformer l'entrée $T$ d'un problème de la recherche du minimum dans un tableau d'entiers positifs par une entrée $T'$ du problème de la recherche du maximum dans un tableau d'entiers positifs,
  2. utiliser le maximum de $T'$ pour trouver le minimum de $T$

Quelle est la complexité de cet algorithme en fonction de la complexité de l'algorithme utilisé pour rechercher le maximum dans un tableau d'entiers relatifs ?

corrigé

On ne peut plus prendre juste l'opposé. Mais comme on peut utiliser l'algorithme $\max(T)$, on peut toujours prendre le tableau $T'$ comme étant $T'[x] = \max(T)-T[x]$ et on cherche $\max(T')$. Le min est alors : $\min(T) = \max(T)-\max(T')$.

La complexité de passer de $T$ à $T'$ est $\mathcal{O}(n) + C'{\max}(n)$ (on ne calcule le max qu'une seule fois) avec $n$ la longueur de $T$ et comme $\min(T) = \max(T)-\max(T')$, la complexité de passer d'une solution à l'autre est encore $C{\max}(n)$. La complexité totale est alors (en notant $C_{\min}(n)$ et $C_{\max}(n)$ la complexité des deux algorithme de résolution) :

$$ C'_{\min}(n) = \mathcal{O}(n) + C'_{\max}(n) = C'_{\max}(n) $$

Puisque on a vu dans l'exercice précédent que la recherche du maximum d'un tableau est toujours au moins linéaire.

Selon la complexité des conversions, la complexité du problème général peut-être plus grande que celle du cas particulier. Pour palier ça, on définie un autre type de comparaison, la réduction.

La réduction

Commençons par définir le cadre général de la réduction :

Définition

Soient $P_1$ et $P_2$ deux problèmes algorithmiques. Une réduction de $P_1$ en $P_2$ est un couple d'algorithmes $A_{1\rightarrow 2}$ et $A_{2\rightarrow 1}$ tels que :

  • Si $E_1$ est une entrée du problème $P_1$ alors $A_{1\rightarrow 2}(E_1)$ est une entrée de du problème $P_2$
  • Si $S_2$ est une solution au problème $P_2$ avec $A_{1\rightarrow 2}(E_1)$ comme entrée alors $A_{2\rightarrow 1}(E_1, S_2)$ est une solution au problème $P_1$ d'entrée $E_1$.

Les réductions forment un ordre sur les problèmes algorithmiques : s'il existe une réduction de $P_1$ en $P_2$ on notera $P_1 \leq P_2$.

La définition formelle ci-dessus est équivalente à :

À retenir

Une réduction de $P_1$ en $P_2$ signifie que l'on utilise le problème $P_2$ (potentiellement un nombre constant de fois) pour résoudre le problème $P_1$.

Pour qu'une réduction ait un sens, il faut que les passages entre les problème $P_1$ et $P_2$ soit de faible complexité. En effet, en notant $C_{P_1}(n)$, $C_{1\rightarrow 2}(n)$, $C_{P_2}(n)$ et $C_{2\rightarrow 1}(n)$ les complexités des algorithmes $P_1$, $A_{1\rightarrow 2}$, $P_2$ et $A_{2\rightarrow 1}$ respectivement on a :

$$ C_{P_1}(n) = C_{1\rightarrow 2}(n) + C_{P_2}(n') + C_{2\rightarrow 1}(n'' + n) $$

Avec :

Notez bien que comme on cherche à borner la complexité du problème $P_1$, toutes nos complexité doivent dépendre uniquement de $n$ qui est la taille de l'entrée de $P_1$. Selon les complexités de l'aller retour entre $P_1$ et $P_2$ cela va être plus ou moins facile. On défini alors :

Définition

Une réduction polynomiale du problème algorithmique $P_1$ au problème algorithmique $P_2$ est une réduction où les passages du problème $P_1$ au problème $P_2$ et du problème $P_2$ au problème $P_1$ sont polynomiales.

On peut sur le même schéma définir une réduction linéaire (les passages sont de complexité linéaire), reduction logarithmique (les passages sont de complexité logarithmique par rapport à la aille de l'entrée), etc. Borner les passages nous permet de faire des démonstration de complexité en utilisant les complexités du problème $P_2$. Par exemple :

Donnez une réduction en temps constant du problème de recherche du maximum dans un tableau d'entiers au problème du tri d'un tableau d'entiers.

corrigé
  • même entrée pour l'algorithme du max et du tri : $\mathcal{O}(1)$
  • la sortie du max est le plus grand élément de la sortie du tri : $\mathcal{O}(1)$

La réduction polynomiale permet de borner la complexité du problème $P_1$ si la complexité du problème $P_2$ est également polynomiale :

Proposition

S'il existe une réduction polynomiale entre $P_1$ et $P_2$ et que la complexité du problème $P_2$ est polynomiale, alors la complexité du problème $P_1$ est également polynomiale.

preuve

En reprenant les notations précédentes :

  • aller du problème $P_1$ au problème $P_2$ avec une complexité $C_{1\rightarrow 2}(n) = \mathcal{O}(n^k)$
  • résoudre $P_2$ avec une complexité $C_{P_2}(f(n))$. Comme le problème $P_2$ est polynomial on a $C_{P_2}(f(n)) = \mathcal{O}(f(n)^{k'})$ et comme la taille de la sortie de l'algorithme $A_{1\rightarrow 2}$ est au plus $\mathcal{O}(n^k)$ on a : $C_{P_2}(f(n)) = \mathcal{O}(n^{k\cdot k'})$
  • revenir au problème $P_1$ avec une complexité $C_{2\rightarrow 1}(g\circ f(n) + n)$. Comme cette complexité est aussi polynomiale, disons $C_{2\rightarrow 1}(g\circ f(n) + n) = \mathcal{O}(f(n)^{k''})$, on a au final que $C_{2\rightarrow 1}(g\circ f(n)) = \mathcal{O}(n^{k\cdot k'\cdot k''})$

La complexité totale est alors de : $\mathcal{O}(n^{k\cdot k'\cdot k''})$ ce qui est toujours polynomial.

La proposition précédente donne le but de toute réduction. Si la complexité du problème $P_2$ est identique au type de réduction (polynomiale, linéaire, logarithmique, etc) alors la complexité du problème $P_1$ l'est aussi : c'est donc un outil de preuve de complexité puissant.

Entraînons nous sur un petit exemple qui va nécessiter d'utiliser et la sortie de $P_2$ et l'entrée $E_1$ pour trouver $S_1$ :

Montrez que le problème de la recherche de doublon dans un tableau d'entiers (on cherche deux indices différents de même valeur) est plus simple que le problème du tri d'un tableau d'entiers.

corrigé
  • même entrée pour l'algorithme du max et du tri : $\mathcal{O}(1)$
  • on parcourt le tableau trié jusqu'à trouver deux éléments successifs égaux : $\mathcal{O}(n)$ avec $n$ taille du tableau en entrée. On note $\alpha$ cette valeur.

Il faut ensuite retrouver, dans le tableau d'entrée 2 indices différents valant la valeur $\alpha$, ce qui peut se faire en $\mathcal{O}(n)$ en parcourant tous les indices de $T$ :


a, b <- 0
pour chaque i de [0 .. T.longueur]:
  si T[i] == α:
    b <- a
    b <- i

rendre b, a

Comme on sait que la valeur $\alpha$ va apparaître (au moins) 2 fois, le code précédent va donner deux indice différents de $T$ dont la valeur vaut $\alpha$.

Exemples et exercices

Produit et carré

Montrer que le problème d'élever un entier au carré est équivalent au problème de multiplier deux entiers entres eux.

corrigé

Soit $C(x)$ un algorithme qui rend $x^2$ et $M(x, y)$ un algorithme qui rend $xy$.

Comme $C(x) = M(x, x)$ on a clairement $C \leq M$.

La réciproque vient du produit remarquable $(x + y)^2 = x^2 + y^2 + 2xy$ et donc $M(x, y) = \frac{1}{2}(C(x+y) - C(x) - C(y))$.

{2, 3}-SUM

Nous allons voir ici une chaîne de réductions, qui nous serons utiles plus tard. On reprend les problèmes 2-SUM et 3-SUM que l'on a déjà vu et on montre qu'ils sont équivalents à d'autres problèmes.

2-SUM = crédit

Un petit échauffement :

Montrer que 2-SUM est équivalent au problème crédit en prenant l'ordre des réductions linéaires

corrigé
  • 2-SUM ≤ crédit : on prend C=0
  • crédit ≤ 2-SUM : on retranche C/2 à tous les prix

2-SUM ≤ ÉGAL

Commençons par le problème 2-SUM et regardons un problème qui lui ressemble :

Problème

  • nom : ÉGAL
  • Entrées :
    • $T$, $T'$ : deux tableaux d'entiers relatifs
  • question : existe-t-il 2 indices tels que $T[i] = T'[j]$

Montrez que :

Montrer que 2-SUM ≤ ÉGAL pour l'ordre des réductions linéaires

corrigé

On prend $T'$ le tableau tel que $T'[k] = -T[k]$ pour tout indice $k$

3-SUM ≤ 3-SUM'

Continuons sur notre lancée avec 3-SUM en considérant le problème suivant :

Problème

  • Nom : 3-SUM'
  • Entrées :
    • $T$, $T'$ et $T''$ : trois tableaux d'entiers relatifs
  • Question : existe-t-il 3 indices tels que $T[i] + T'[j] = T''[k]$

Qui, selon toute logique doit être plus général que 3-SUM. Montrez le :

Montrer que 3-SUM ≤ 3-SUM' l'ordre des réductions linéaires

corrigé

On prend $T = T'$ et $T''[x] = -T[x]$

Problèmes équivalents ?

Montrons que les versions alternatives des problèmes 2-SUM (ÉGAL) et 3-SUM (3-SUM') sont équivalents aux problèmes d'origine pour l'ordre des réductions linéaires. Ces réductions vont nécessiter un peu de travail.

Montrer que ÉGAL ≤ 2-SUM

Il faudra placer les deux tableaux du problème ÉGAL dans l'unique tableau d'entrée de 2-SUM sans que les indices de la solution de 2-SUM ne correspondent au même tableau initial.

Vous pourrez procéder en 2 temps :

  1. proposez une solution qui fonctionne si les 2 tableaux $T$ et $T'$ en entrée de ÉGAL sont tels que $T[i] + T[j] \neq 0$ et $T'[i] + T'[j] \neq 0$ pour tous $i$ et $j$
  2. prouver que l'on peut toujours se ramener au cas précédent en ajoutant une valeur $A$ à chaque valeur de $T$ et en retranchant cette valeur $A$ à tous les éléments de $T'$

corrigé

Il faut commencer par mettre 2 tableaux dans un seul en définissant un tableau $T''$ dont les premiers éléments sont liés a $T$ et les derniers à $T'$. On ne peut prendre directement :

  • $T''[i] = T[i]$ pour $0 \leq i < T.\mbox{\small longueur}$
  • $T''[T.\mbox{\small longueur} + j] = T'[j]$ pour $0 \leq j < T'.\mbox{\small longueur}$

Car l'égalité pourrait arriver pour deux indices du même tableau initial. On prend donc :

  • $T''[i] = T[i] + A$ pour $0 \leq i < T.\mbox{\small longueur}$
  • $T''[T.\mbox{\small longueur} + j] = T'[j] - A$ pour $0 \leq j < T'.\mbox{\small longueur}$

Avec $A$ assez grand pour que $2A > T[i] + [j]$ et $2A > T'[i] + T'[j]$ pour tous $i$ et $j$ ce qui impliquera que si $T''[i] + T''[j] = 0$ alors $0 \leq i < T.\mbox{\small longueur} \leq j$ (ou réciproquement).

Si on prend $A = 2(\sum \vert T[i]\vert + \sum \vert T'[i]\vert) + 1$ cela va fonctionner.

On peut ensuite utiliser la même astuce que précédemment pour résoudre :

Montrer que 3-SUM' ≤ 3-SUM

corrigé

On procède (bien sur) comme précédemment en adaptant à trois tableaux. On choisit $A = 3(\sum \vert T[i]\vert + \sum \vert T'[i]\vert + \sum \vert T''[i]\vert) + 1$ et on crée un tableau $T'''$ tel que :

  • $T'''[i] = T[i] + A$ pour $0 \leq i < T.\mbox{\small longueur}$
  • $T'''[T.\mbox{\small longueur} + j] = T'[j] + 3\cdot A$ pour $0 \leq j < T'.\mbox{\small longueur}$
  • $T'''[T.\mbox{\small longueur} + T'.\mbox{\small longueur} + k] = T''[k] - 4\cdot A$ pour $0 \leq k < T''.\mbox{\small longueur}$

Ceci va garantir le fait que si on a 3 indices $i, j, k$ tels que $T'''[i] + T'''[j] + T'''[k] = 0$. on a bien (à ue permutation prêt) :

  • $0 \leq i < T.\mbox{\small longueur}$
  • $T.\mbox{\small longueur} \leq j < T.\mbox{\small longueur} + T'.\mbox{\small longueur}$
  • $T.\mbox{\small longueur} + T'.\mbox{\small longueur} \leq k < T.\mbox{\small longueur} + T'.\mbox{\small longueur} + T''.\mbox{\small longueur}$

3-SUM et géométrie algébrique

3-SUM est un problème fondamental en géométrie algébrique. Considérons par exemple le problème suivant :

Problème

  • nom : GEOBASE
  • Entrées : Un ensemble de $n$ points du plan à coordonnées entières sur trois lignes horizontales avec $y = 0$, $y = 1$ et $y = 2$
  • question : Existe-t-il une droite non horizontale passant par 3 points.

On va montrer en plusieurs étapes qu'il est équivalent à 3-SUM' !

Montrez que deux vecteurs $\vec{u} = (x, y)$ et $\vec{v} = (x', y')$ sont colinéaires si $xy' - yx' = 0$.

Vous pourrez utiliser le fait que deux vecteurs $\vec{u} = (x, y)$ et $\vec{v} = (x', y')$ sont colinéaires si $\vec{u} \cdot \vec{v}^{\perp} = 0$.

corrigé

Deux vecteurs $\vec{u} = (x, y)$ et $\vec{v} = (x', y')$ sont colinéaires si $\vec{u} \cdot \vec{v}^{\perp} = 0$. Comme $\vec{v}^{\perp} = (-y', x')$, $\vec{u}$ et $\vec{v}$ sont colinéaires si $xy' - yx' = 0$.

Poursuivons dans cette optique :

Montrez que les 3 points $A = (x, 0)$, $B = (y, 1)$ et $C = (z, 2)$ sont alignés si et seulement si : $2y = x + z$

corrigé

En utilisant l'exercice précédent, $A$, $B$ et $C$ sont alignés si $\vec{AB} = (y-x, 1)$ et $\vec{BC} = (z-y, 1)$ sont colinéaires donc si : $y-x -(z-y) = 0$

Vous devez avoir assez de billes pour montrer les 2 réductions linéaires :

Montrer que 3-SUM' ≤ GEOBASE pour une réduction linéaire

corrigé

Il suffit alors de construire les points :

  • $(T[i], 0)$
  • $(T''[i]/2, 1)$
  • $(T'[i], 2)$

si trois points sont colinéaires alors il existe i, j et k tels que $T[i] + T'[j] = T''[k]$

Montrer que GEOBASE ≤ 3-SUM' pour une réduction linéaire

corrigé

On fait le contraire. On ajoute chaque point de :

  • $(x, 0)$ dans $T = [x | \forall (x, 0)]$
  • $(x, 1)$ dans $T'' = [2x | \forall (x, 1)]$
  • $(x, 2)$ dans $T' = [x | \forall (x, 2)]$

Et enfin l'équivalence :

Montrer que 3-SUM = GEOBASE pour l'ordre des réductions linéaires.

corrigé

Clair puisque 3-SUM = 3-SUM' = GEOBASE

Si ce genre de problème de géométrie solvable algébriquement, n'hésitez pas à jeter un coup d'œil aux liens suivants :