Réduction polynomiale et NP-complétude

1. La Réduction Polynomiale : Formalisme

Nous avons effleuré ce concept la dernière fois. Une réduction polynomiale d'un problème A à un problème B est un algorithme qui transforme, en temps polynomial, toute instance $x$ de A en une instance $f(x)$ de B, tout en préservant la réponse : $x$ est une instance "oui" de A si et seulement si $f(x)$ est une instance "oui" de B.

Cette relation, notée $A{\le }_{p}B$, signifie que B est au moins aussi difficile que A. Si l'on disposait d'un algorithme efficace pour B (un "porc sifflant", pour reprendre une analogie classique), on en déduirait un algorithme efficace pour A (un "cheval volant").

Pour une définition formelle et rigoureuse de ce concept, je vous invite à étudier le texte suivant, qui est une référence en la matière.

2. Prouver la NP-complétude par Réduction

Rappelons la stratégie en deux temps pour prouver qu'un problème B est NP-complet :

1. Montrer que B est dans NP. En général, cela consiste à montrer qu'une solution candidate ("certificat") peut être vérifiée en temps polynomial.
2. Montrer que B est NP-difficile. Pour cela, on choisit un problème A que l'on sait déjà NP-complet (par exemple, SAT) et on prouve que $A{\le }_{p}B$.

Par transitivité, si tout problème de NP se réduit à A, et que A se réduit à B, alors tout problème de NP se réduit à B.

3. Étude de Cas : La Réduction de SAT à 3-SAT

Armés de cette stratégie, attaquons notre objectif : prouver que 3-SAT est NP-complet.

• Le problème 3-SAT : Étant donné une formule booléenne en forme normale conjonctive (FNC) où chaque clause contient exactement trois littéraux, la formule est-elle satisfiable ?

Étape 1 : 3-SAT est dans NP
Ceci est direct. Si l'on nous donne une assignation des variables (le certificat), il suffit de parcourir la formule et de vérifier pour chaque clause si elle est évaluée à VRAI. Cette vérification est linéaire en la taille de la formule, donc polynomiale.

Étape 2 : 3-SAT est NP-difficile (via SAT ${\le }_p$ 3-SAT)
C'est le cœur de la preuve. Nous devons construire un algorithme qui prend n'importe quelle formule $\varphi$ de SAT (avec des clauses de n'importe quelle taille) et la transforme en une formule ${\varphi }^{\prime }$ de 3-SAT, de sorte que $\varphi$ est satisfiable si et seulement si ${\varphi }^{\prime }$ l'est.

La difficulté est que la transformation doit être polynomiale. Une approche naïve utilisant les lois de distributivité pour convertir la formule en FNC peut entraîner une explosion exponentielle de la taille de la formule. Il faut une approche plus subtile.

La technique clé consiste à introduire des variables auxiliaires pour décomposer les clauses qui ne respectent pas la contrainte de taille.

Le document suivant, issu d'un cours de l'IRIF, détaille cette construction de manière exemplaire et correspond parfaitement au niveau d'exigence de l'Agrégation.

Synthétisons et analysons cette transformation pour une clause $C$ de $\varphi$ de taille $k$.

Transformation des clauses

• Si $k=3$ : La clause est déjà au format 3-SAT. On la conserve telle quelle.

• Si $k=1$ : La clause est $(l_1)$. On la remplace par $(l_1\vee l_1\vee l_1)$. Plus formellement, pour ne pas dépendre de la sémantique de la répétition, on introduit deux variables nouvelles $a,b$ et on la remplace par la conjonction de quatre clauses :

  $$(l_1\vee a\vee b)\wedge (l_1\vee a\vee \neg b)\wedge (l_1\vee \neg a\vee b)\wedge (l_1\vee \neg a\vee \neg b)$$

  Cette nouvelle formule est satisfiable si et seulement si $l_1$ est VRAI. Une version plus simple, et suffisante, est $(l_1\vee a\vee \neg a)$, qui est une tautologie si on la considère seule, mais qui, dans la pratique, est souvent simplifiée à une technique de "padding" comme $(l_1\vee l_1\vee l_1)$. La méthode la plus rigoureuse est la première, mais la plus commune dans les preuves est de répéter les littéraux.

• Si $k=2$ : La clause est $(l_1\vee l_2)$. On la remplace par $(l_1\vee l_2\vee l_1)$ ou, de manière plus formelle, $(l_1\vee l_2\vee a)\wedge (l_1\vee l_2\vee \neg a)$.

• Si $k>3$ : La clause est $(l_1\vee l_2\vee \cdots \vee l_k)$. C'est le cas le plus instructif. On la remplace par une conjonction de $k-2$ clauses de 3 littéraux en introduisant $k-3$ nouvelles variables $y_1,y_2,\dots ,y_{k-3}$.

  $$(l_1\vee l_2\vee y_1)\wedge (\neg y_1\vee l_3\vee y_2)\wedge (\neg y_2\vee l_4\vee y_3)\wedge \cdots \wedge (\neg y_{k-3}\vee l_{k-1}\vee l_k)$$

La vidéo suivante illustre très bien ce processus de transformation.

Analyse de la transformation

Pourquoi cette transformation est-elle une réduction polynomiale valide ?

1. Préservation de la satisfiabilité :
   • Si $\varphi$ est satisfiable, au moins un littéral $l_i$ dans chaque clause est vrai. On peut alors choisir des valeurs pour les variables $y_j$ qui satisfont la chaîne de clauses. Par exemple, si $l_3$ est vrai, on peut poser $y_1=\text{VRAI}$ (satisfait la 1ère clause) et $y_2=\text{FAUX}$ (la 2ème clause est satisfaite par $l_3$). On peut propager ces choix.
   • Si ${\varphi }^{\prime }$ est satisfiable, supposons par l'absurde que tous les $l_i$ d'une clause originale sont faux. Dans la nouvelle chaîne de clauses, pour que $(l_1\vee l_2\vee y_1)$ soit vraie, $y_1$ doit être VRAI. Pour que $(\neg y_1\vee l_3\vee y_2)$ soit vraie, $y_2$ doit être VRAI. En propageant, on arrive à la dernière clause $(\neg y_{k-3}\vee l_{k-1}\vee l_k)$ qui devient $(\text{FAUX}\vee \text{FAUX}\vee \text{FAUX})$, une contradiction. Donc au moins un $l_i$ doit être vrai.
2. Efficacité polynomiale : Pour chaque clause de $\varphi$, on crée un nombre de nouvelles clauses et de nouvelles variables qui est linéaire en la taille de la clause initiale. L'ensemble de l'algorithme s'exécute donc en temps polynomial par rapport à la taille de $\varphi$.

Puisque 3-SAT est dans NP et que nous avons montré SAT ${\le }_p$ 3-SAT, nous pouvons conclure que 3-SAT est NP-complet.

4. L'Anatomie d'une Preuve par Réduction

La démonstration que nous venons de voir est un modèle pour de nombreuses autres preuves de NP-complétude. Il est utile de décomposer sa structure pour pouvoir la reproduire.

Toute preuve de réduction $A{\le }_{p}B$ doit contenir ces quatre éléments :

1. Description de l'algorithme : Description précise de la fonction de transformation $f$ qui mappe une instance de A vers une instance de B.
2. Analyse de l'efficacité : Preuve que $f$ s'exécute en temps polynomial.
3. Preuve de complétude (Completeness) : Démontrer que si une instance $x$ de A a une solution, alors l'instance transformée $f(x)$ de B a aussi une solution.
4. Preuve de robustesse (Soundness) : Démontrer que si l'instance transformée $f(x)$ de B a une solution, alors l'instance originale $x$ de A avait aussi une solution.

En appliquant cela à notre exemple SAT ${\le }_p$ 3-SAT :

1. Algorithme : Remplacer chaque clause de taille $k\ne 3$ par un ensemble équivalent de clauses de taille 3.
2. Efficacité : La transformation est linéaire pour chaque clause, donc polynomiale au total.
3. Complétude : Si une assignation satisfait la clause originale, nous avons montré comment assigner les variables auxiliaires pour satisfaire les nouvelles clauses.
4. Robustesse : Si les nouvelles clauses sont satisfaites, nous avons montré par un argument en chaîne qu'au moins un des littéraux originaux doit être vrai.

Conclusion

Cette leçon vous a armé d'une méthode de preuve fondamentale en informatique théorique. La réduction polynomiale n'est pas seulement un artifice technique ; c'est une manière de raisonner sur la structure intrinsèque des problèmes.

Points clés à retenir :

• Une réduction polynomiale $A{\le }_{p}B$ est un algorithme polynomial qui traduit les instances de A en instances de B tout en préservant la réponse. Elle prouve que B est au moins aussi difficile que A.
• Pour prouver qu'un problème B est NP-complet, la méthode standard est de prouver que $B\in \text{NP}$ et de trouver un problème A déjà connu comme NP-complet tel que $A{\le }_{p}B$.
• La réduction de SAT à 3-SAT est un exemple canonique qui utilise la technique puissante de l'introduction de variables auxiliaires pour restructurer les contraintes d'un problème.
• Une preuve de réduction rigoureuse comporte systématiquement quatre parties : description, efficacité, complétude et robustesse.

Dans notre prochaine leçon, nous changerons radicalement de sujet pour aborder le dernier module de notre programme de fondations. Nous délaisserons la théorie de la complexité pour nous plonger dans un nouveau paradigme de programmation avec l'introduction à la programmation fonctionnelle en OCaml. La maîtrise de plusieurs paradigmes étant une compétence clé pour l'Agrégation, cette transition est une étape logique de votre préparation.