Chapitre 12 : Quelques problèmes NP-complets

Ce laboratoire explore plusieurs problèmes NP-complets célèbres en informatique théorique et en optimisation combinatoire. Il présente des définitions formelles, des démonstrations de NP-complétude par réduction, ainsi que des liens entre ces problèmes. Ce TP permet de comprendre les concepts clés de la NP-complétude, les techniques de réduction polynomiale, et la complexité de certains problèmes classiques. Pour suivre ce TP, il est nécessaire d’avoir des connaissances de base en logique, en théorie des graphes, et en complexité algorithmique.

Objectifs

• Comprendre la définition et la signification des problèmes NP-complets.
• Apprendre à effectuer des réductions polynomiales entre problèmes.
• Étudier plusieurs problèmes NP-complets classiques : 3-SAT, NAESAT, STABLE, CLIQUE, RECOUVREMENT DE SOMMETS, COUPURE MAXIMALE, CIRCUIT HAMILTONIEN, VOYAGEUR DE COMMERCE, 3-COLORABILITE, SOMME DE SOUS-ENSEMBLE, SAC A DOS, PARTITION.
• Analyser les relations entre ces problèmes et leurs démonstrations de NP-complétude.
• Se familiariser avec les techniques de preuve par réduction et les implications en complexité.

Prérequis et installation

• Connaissances en logique propositionnelle et en formules booléennes.
• Notions de théorie des graphes : sommets, arêtes, cliques, stable, cycles hamiltoniens.
• Compréhension des classes de complexité P, NP, et du concept de NP-complétude.
• Pas de logiciel spécifique requis : ce TP est théorique et basé sur des démonstrations formelles.

Problèmes autour de SAT

Nous commençons par le problème 3-SAT, une version restreinte de SAT où chaque clause contient exactement trois littéraux.

Définition 12.1 (3-SAT)

Donnée : un ensemble de variables {x1, ..., xn} et une formule F = C1 ∧ C2 ∧ ... ∧ Cm avec chaque clause Ci = yi,1 ∨ yi,2 ∨ yi,3, où chaque littéral yi,j est soit xk, soit ¬xk.

Réponse : décider s’il existe une affectation des variables x1, ..., xn dans {0,1} telle que F soit vraie.

Théorème 12.1 : 3-SAT est NP-complet.

Preuve : 3-SAT est dans NP car une affectation est un certificat vérifiable en temps polynomial. La réduction de SAT à 3-SAT se fait en remplaçant chaque clause longue par une conjonction de clauses à trois littéraux, en introduisant de nouvelles variables auxiliaires. Par exemple, une clause C = x ∨ y ∨ z ∨ u ∨ v ∨ w ∨ t est remplacée par :

(x ∨ y ∨ a) ∧ (¬a ∨ z ∨ b) ∧ (¬b ∨ u ∨ c) ∧ (¬c ∨ v ∨ d) ∧ (¬d ∨ w ∨ t)

Cette transformation est polynomiale et préserve la satisfaisabilité.

Remarque : Le problème 2-SAT, où les clauses ont deux littéraux, est dans P.

Définition 12.2 (NAESAT)

Donnée : un ensemble de variables {x1, ..., xn} et un ensemble de clauses yi,1 ∨ ... ∨ yi,ki, où chaque littéral est xk ou ¬xk.

Réponse : décider s’il existe une affectation des variables telle que dans chaque clause il y ait au moins un littéral vrai et au moins un littéral faux.

Théorème 12.2 : NAESAT est NP-complet.

Preuve : NAESAT est dans NP. La réduction de SAT à NAESAT s’effectue en ajoutant une variable z à chaque clause. Si SAT est satisfaisable, on fixe z = 0 pour obtenir une affectation valide pour NAESAT. Réciproquement, si NAESAT est satisfaisable, on peut ajuster l’affectation pour que z = 0, ce qui donne une affectation satisfaisant SAT.

De plus, NAE4SAT est NP-complet, et on réduit NAE4SAT à NAE3SAT en divisant chaque clause à 4 littéraux en deux clauses à 3 littéraux en introduisant une variable auxiliaire uC :

C1 = x ∨ y ∨ ¬uC
C2 = z ∨ t ∨ uC

Cette réduction est polynomiale et prouve que NAE3SAT est NP-complet.

Problèmes autour de STABLE

Définition 12.3 (STABLE)

Donnée : un graphe non orienté G = (V, E) et un entier k.

Réponse : décider s’il existe un sous-ensemble V' ⊂ V de taille k tel que pour tout u, v ∈ V', (u, v) ∉ E (c’est-à-dire un stable ou ensemble indépendant).

Théorème 12.3 : STABLE est NP-complet.

Preuve : STABLE est dans NP. La réduction de 3-SAT à STABLE consiste à construire un graphe G avec un sommet par littéral dans chaque clause. On relie les littéraux contradictoires par des arêtes, et chaque clause forme un triangle. Un stable de taille k correspond à une affectation satisfaisant la formule.

Définition 12.4 (CLIQUE)

Donnée : un graphe G = (V, E) et un entier k.

Réponse : décider s’il existe un sous-ensemble V' ⊂ V de taille k tel que pour tout u, v ∈ V', (u, v) ∈ E (c’est-à-dire une clique).

Théorème 12.4 : CLIQUE est NP-complet.

Preuve : La réduction de STABLE à CLIQUE se fait en considérant le graphe complémentaire.

Définition 12.5 (RECOUVREMENT DE SOMMETS)

Donnée : un graphe G = (V, E) et un entier k.

Réponse : décider s’il existe un sous-ensemble V' ⊂ V de taille ≤ k tel que toute arête ait au moins une extrémité dans V'.

Théorème 12.5 : RECOUVREMENT DE SOMMETS est NP-complet.

Preuve : Réduction à partir de STABLE par complémentaire sur les sommets.

Définition 12.6 (COUPURE MAXIMALE)

Donnée : un graphe G = (V, E) et un entier k.

Réponse : décider s’il existe une partition V = V1 ∪ V2 telle que le nombre d’arêtes entre V1 et V2 soit au moins k.

Théorème 12.6 : COUPURE MAXIMALE est NP-complet.

Preuve : Réduction de NAE3SAT à COUPURE MAXIMALE. On construit un graphe où chaque clause correspond à un triangle, et chaque variable à deux sommets reliés. Le nombre d’arêtes dans une coupure maximale correspond à une affectation satisfaisant NAE3SAT.

Problèmes autour de CIRCUIT HAMILTONIEN

Définition 12.7 (CIRCUIT HAMILTONIEN)

Donnée : un graphe non orienté G = (V, E).

Réponse : décider s’il existe un circuit passant une fois par chaque sommet et revenant au point de départ.

Théorème 12.7 : CIRCUIT HAMILTONIEN est NP-complet.

Preuve : Réduction de RECOUVREMENT DE SOMMETS à CIRCUIT HAMILTONIEN. Chaque arête est remplacée par un motif complexe admettant deux chemins hamiltoniens, selon que le sommet appartient ou non à la couverture. Le graphe final H est construit en reliant ces motifs et en ajoutant k sommets spéciaux. Un circuit hamiltonien dans H correspond à une couverture de taille k dans G.

Définition 12.8 (VOYAGEUR DE COMMERCE)

Donnée : un entier n, une matrice M n × n d’entiers, et un entier k.

Réponse : décider s’il existe une permutation π de [1,...,n] telle que la somme des distances Mπ(i)π(i+1) soit ≤ k.

Corollaire 12.2 : VOYAGEUR DE COMMERCE est NP-complet.

Preuve : Réduction de CIRCUIT HAMILTONIEN à VOYAGEUR DE COMMERCE en posant Mij = 1 si (i,j) ∈ E, sinon 2. Un circuit hamiltonien correspond à une permutation de coût n.

Définition 12.9 (CIRCUIT LE PLUS LONG)

Donnée : un graphe G = (V, E) avec des distances sur les arêtes, un entier r.

Réponse : décider s’il existe un circuit passant une fois par chaque sommet de longueur ≥ r.

Corollaire 12.3 : CIRCUIT LE PLUS LONG est NP-complet.

Preuve : Réduction de CIRCUIT HAMILTONIEN en attribuant un poids 1 à chaque arête.

Problèmes autour de 3-COLORABILITE

Définition 12.10 (3-COLORABILITE)

Donnée : un graphe non orienté G = (V, E).

Réponse : décider s’il existe un coloriage des sommets avec au plus 3 couleurs telles que deux sommets adjacents n’aient pas la même couleur.

Théorème 12.8 : 3-COLORABILITE est NP-complet.

Preuve : Réduction de 3-SAT à 3-COLORABILITE. On construit un graphe avec trois sommets VRAI, FAUX, NSP formant un triangle, imposant trois couleurs distinctes. Chaque variable et son complémentaire forment un triangle avec NSP, forçant une coloration opposée. Les clauses sont modélisées par un motif spécifique garantissant que si le graphe est 3-coloriable, alors la formule est satisfaisable, et inversement.

Problèmes autour de SOMME DE SOUS-ENSEMBLE

Définition 12.11 (SOMME DE SOUS-ENSEMBLE)

Donnée : un ensemble fini d’entiers E et un entier t.

Réponse : décider s’il existe un sous-ensemble E' ⊂ E tel que la somme des éléments de E' soit égale à t.

Théorème 12.9 : SOMME DE SOUS-ENSEMBLE est NP-complet.

Preuve : Réduction de RECOUVREMENT DE SOMMETS à SOMME DE SOUS-ENSEMBLE. On associe à chaque sommet un entier codé en base b ≥ 4, avec des coefficients correspondant aux arêtes incidentes. Le but est de trouver un sous-ensemble dont la somme encode une couverture de sommets de taille k. On ajoute aussi des entiers correspondant aux arêtes pour contourner certaines contraintes.

Définition 12.12 (SAC A DOS)

Donnée : un ensemble de poids a1,...,an, un ensemble de valeurs v1,...,vn, un poids limite A, et un entier V.

Réponse : décider s’il existe un sous-ensemble E' ⊂ {1,...,n} tel que la somme des poids soit ≤ A et la somme des valeurs ≥ V.

Corollaire 12.4 : SAC A DOS est NP-complet.

Preuve : Réduction de SOMME DE SOUS-ENSEMBLE en posant ai = vi = ei, A = V = t.

Définition 12.13 (PARTITION)

Donnée : un ensemble fini d’entiers E.

Réponse : décider s’il existe un sous-ensemble E' ⊂ E tel que la somme des éléments de E' soit égale à la somme des éléments de E \ E'.

Théorème 12.10 : PARTITION est NP-complet.

Preuve : Réduction de SOMME DE SOUS-ENSEMBLE à PARTITION. On construit un ensemble E' = E ∪ {X, X'} avec X = 2S et X' = S + 2t, où S est la somme des éléments de E. Une partition de E' correspond à un sous-ensemble de E de somme t. La réduction est polynomiale.

Résultats attendus

• Compréhension claire des définitions formelles des problèmes NP-complets présentés.
• Maîtrise des techniques de réduction polynomiale entre problèmes.
• Capacité à suivre et reproduire les démonstrations de NP-complétude.
• Identification des relations entre problèmes classiques (ex. STABLE et CLIQUE, CIRCUIT HAMILTONIEN et VOYAGEUR DE COMMERCE).
• Connaissance des implications pratiques en complexité algorithmique.

Pièges courants

• Confondre les différentes classes de complexité (P, NP, NP-complet).
• Omettre la vérification que la réduction est bien polynomiale.
• Ne pas distinguer entre les différentes versions d’un problème (ex. 2-SAT vs 3-SAT).
• Mal interpréter la construction des graphes dans les réductions (ex. motifs pour CIRCUIT HAMILTONIEN).
• Ignorer les conditions spécifiques dans les réductions, comme l’ajout de variables auxiliaires ou la transformation des clauses.
• Penser qu’une réduction prouve que le problème est dans P, alors qu’elle montre seulement la NP-complétude.