L3 – Algorithmique 1 (Année 2018/2019) Marc de Visme & Laureline Pinault

TD 08 – NP-Complétude, encore (corrigé)

(SatN) Exercice 1. Echauffement

On appelle SAT-N le problème SAT restreint aux formules qui n’ont pas plus de N occurrences de la
même variable.
1. Montrer que SAT-3 est au moins aussi dur que SAT. En déduire que pour tout N ≥ 3, SAT-N est
N P -complet.
+ SAT-3 est trivialement NP.
Pour montrer qu’il est NP-complet, on part d’un problème de SAT et pour chaque littéral xi apparaissant k fois avec k avec k > 3
, on applique l’algorithme suivant : on remplace les occurrences de xi par k nouveaux littéraux yi1 , . . . , yik , et on rajoute les clauses
yi1 ∨ yi2 , . . . , yik−1 ∨ yik et yik ∨ yi1 .
Les nouveaux littéraux apparaissent alors 3 fois chacun (une fois à la place de xi , et deux fois dans les nouvelles clauses). De plus les
nouvelles clauses entraînent que les yi j prennent tous la même valeur : si yi j est vrai, alors yi j−1 également, et inversement, si yi j est
faux, alors yi j+1 doit l’être aussi (en toute rigueur on devrait rajouter des modulos k), et comme les clauses sont cycliques, on obtient
que tous ces littéraux ont la même valeur.
Enfin, si n est le nombre de littéraux, et m le nombre de clauses, le nouveau problème obtenu comporte au plus nm littéraux et
(m + nm) clauses, donc une instance de SAT se réduit polynomialement en une instance SAT-3 équivalente, et comme SAT-3 est NP,
SAT-3 est NP-complet.
Et comme pour tout N ≥ 3, SAT-3 est un cas particulier de SAT-N, SAT-N est NP-complet.

2. Soit x une variable apparaissant dans une formule F de SAT-2. Trouver une formule équivalente
à F et dans laquelle la variable x n’apparaisse plus. En déduire un algorithme polynomial pour
SAT-2.
+ Soit x une variable d’un système de clauses F de SAT-2, on transforme F selon les cas de sorte que le système obtenu soit
satisfiable si et seulement si le système initial l’était :
— si x (ou x) n’apparaît qu’une seule fois, on supprime la clause dans laquelle il apparaît, car on est libre de mettre x (ou x), donc
toute la clause à vrai.
— si x (ou bien x) apparaît 2 fois dans une même clause, ou dans 2 clauses distinctes, on supprime la ou les clauses, pour la même
raison.
— si x et x apparaissent dans la même clause, on supprime la clause car elle est toujours à vrai.
— si x et x apparaissent dans 2 clauses distinctes, x ∨ C1 et x ∨ C2 , alors le système de clauses est satisfiable si et seulement si au
moins une des deux clauses C1 ou C2 peut être mise à vrai en même temps que les autres clauses (pour l’autre on choisit x pour
compléter), ainsi :
— → si C1 = C2 = ∅ alors le système n’est pas satisfiable.
— → sinon on remplace les 2 clauses par la nouvelle clause C1 ∨ C2 .
On a ainsi défini un algorithme en n étapes (où n est le nombre de littéraux), pour lequel on décide à chaque étape de la valeur d’un
littéral avec une complexité m (où m est le nombre de clauses) : on peut donc résoudre SAT-2 en O(nm).

(2PartEtAll) Exercice 2. 2 Partitions et ses variantes

On définit les deux problèmes suivants :
SUBSET-SUM
Instance : Un ensemble fini S d’entiers positifs et un entier objectif t.
Question : Existe-t-il un sous-ensemble S0 ⊆ S tel que ∑ x∈S0 x = t ?
2-PARTITION
Instance : S = { a1 , . . . , an } un ensemble d’entier.
Question : Existe-t-il I ⊂ S tel que ∑i∈ I ai = ∑i6∈ I ai ?
On suppose pour l’instant que ces deux problèmes sont NP-Complets. Montrer la NP-Complétude des
problèmes suivants.
1. Etant donnés n entiers a1 , a2 , . . . , an , peut-on trouver un sous-ensemble I ⊂ [1..n] tel que | ∑i∈ I ai −
∑i∈/ I ai | ≤ 1 + ∈ NP : trivial.
Instance I1 de départ : a1 , ...an de 2-partition.
Instance I2 créée : (1664a1 , ...1664an ).
Equivalence : S’il existe I avec ∑i∈ I ai = ∑i∈[1,n]\ I ai , alors | ∑i∈ I ai − ∑i∈[1,n]\ I ai | = 0 ≤ 1
Réciproquement, s’il existe I avec | ∑i∈ I 1664ai − ∑i∈[1,n]\ I 1664ai | ≤ 1, alors on a | ∑i∈ I ai − ∑i∈[1,n]\ I ai | ≤ 1/1664. Or on travaille dans
les entiers, ainsi on aboutit à ∑i∈ I ai = ∑i∈[1,n]\ I ai .

1
 2. Soient n = 2p un entier pair, et n entiers strictement positifs a1 , a2 , . . . , an . Existe-t-il une partition
de {1, 2, . . . n} en deux ensembles I et I 0 de même cardinal p et tels que ∑i∈ I ai = ∑i∈ I 0 ai ? + ∈
NP : trivial.
Instance I1 de départ : a1 , ...an de 2-partition.
Instance I2 créée : ( a1 + 1, ...an + 1, 1, ...1) de cardinal 2n.
Equivalence : Si ∑i∈ I ai = ∑i∈[1,n]\ I ai alors ∑i∈ I ( ai + 1) + (n − | I |) = ∑i∈[1,n]\ I ( ai + 1) + | I |.
Réciproquement, une solution est de la forme ∑i∈ I ( ai + 1) + (n − | I |) = ∑i∈[1,n]\ I ( ai + 1) + | I |. En effet il faut avoir n termes à droite et
à gauche donc il faut rajouter un (n − | I |) à gauche, et | I | ≤ n sinon au n’aurait jamais l’égalité, car tous les ai sont positifs. Ainsi on
a bien ∑i∈ I ai = ∑i∈[1,n]\ I ai

3. Étant donnés n entiers S{ a1 , a2 , . . . , an }, peut-on trouver trois sous-ensembles I1 , I2 et I3 parti-

tionnant [1..n] et tels que ∑i∈ I1 ai = ∑i∈ I2 ai = ∑i∈ I3 ai ?
+ 3-partition appartient à NP : étant donné un certificat on vérifie en temps linéaire que ∑i∈ I1 ai = ∑i∈ I2 ai = ∑i∈ I3 ai .
On va faire une réduction à partir de. . . 2-Partition (étonnant non ?). Pour construire une instance de 3-Partition on prend donc une
instance de 2-Partition avec n entiers S = { a1 , . . . , an }, avec P = ∑in=1 ai et tels que ∀i, ai ≤ P/2 (sinon il n’y a pas de solution), et on
rajoute un nouvel entier an+1 = P/2. Si 2-Partition a une solution I avec l’ensemble initial S, alors il suffit de prendre comme solution
pour 3-Partition : ∑i∈ I ai = ∑i6∈ I ai = an+1 , soit I1 = I, I2 = S\ I et I3 = an+1 .
Réciproquement, si 3-Partition a un solution, alors nécessairement on a I1 ou I2 ou I3 qui est égal à I 0 ∪ an+1 , avec ∑i∈ I 0 ai = 0, et il
suffit de prendre les sous-ensembles restant comme solution de 2-Partition.
Donc 3-Partition est NP-complet.

4. S’agit-il de NP-complétude au sens faible ou au sens fort ?

+ Au sens faible. Prendre l’algo du cours pour 2-Partition et l’adapter pour 3-Partition.

On va maintenant s’intéresser à la NP-Complétude des deux problèmes définis au début de l’exercice.

5. Montrer que 2-Partition est NP-complet. (On pourra supposer la NP-Complétude de SUBSET-
SUM).
+ 2-Partition est trivialement dans NP : on vérifie en temps linéaire qu’un certificat nous donne bien ∑i∈ I ai = ∑i6∈ I ai .
On fait une réduction à partir de SUBSET-SUM. Soit une instance de SUBSET-SUM : on a n entiers S = { a1 , . . . , an }, et un objectif
t. On construit une instance de 2-Partition de la façon suivante :
— si t ≤ ∑in=1 ai < 2t : on pose an+1 = 2t − ∑in=1 ai , et on construit un ensemble S0 = S ∪ { an+1 } pour 2-Partition. On a donc
n +1
∑i=1 ai = 2t. Si on a une solution I1 à SUBSET-SUM telle que ∑i∈ I1 ai = t, alors on a une solution pour 2-Partition en prenant
∑i∈ I1 ai = ∑i∈S0 \ I1 ai = t. Inversement si 2-Partition a une solution, alors nécessairement an+1 ∈ I ou an+1 ∈ S0 \ I, et il suffit de
prendre le sous ensemble de S0 qui ne contient pas an+1 .
— si 2t ≤ ∑in=1 ai : on pose an+1 = ∑in=1 ai − 2t, et on construit l’ensemble S0 comme précédemment. On a donc ∑in=+11 ai = 2 ∑in=1 ai − 2t.
Comme précédemment on a l’équivalence des solutions avec ∑i∈ I1 ai = ∑i∈S0 \ I ai = ∑in=1 ai − t, et donc nécessairement on a soit
1
dans I1 soit dans S0 \ I1 : ∑in=1 ai − 2t + ∑i∈ J ai , et donc l’ensemble J permet d’avoir ∑i∈ J ai = t la solution à SUBSET-SUM.
Donc 2-PARTITION est NP-complet.

6. Montrer que SUBSET-SUM est NP-complet.

Indication : vous pouvez par exemple effectuer une réduction à partir de 3-SAT. A partir d’un
ensemble de clauses C0 , ..., Cm−1 sur les variables x0 , ..., xn−1 , considérer S l’ensemble des entiers
−1 m+i + m−1 b0 10 j , 0 ≤ i ≤ n − 1, où b (resp. b0 ) vaut 1 si le
vi = 10m+i + ∑m j 0
j=0 bij 10 et vi = 10 ∑ j=0 ij ij ij
littéral xi (resp. xi ) apparaît dans Cj et 0 sinon, et des entiers s j = 10 j et s0j = 2.10 j , 0 ≤ j ≤ m − 1.
Trouver alors un entier objectif t tel qu’il existe un sous-ensemble S0 ⊆ S de somme t si et
seulement si l’ensemble initial de clauses est satisfiable. Conclure. Quels autres entiers auraient
aussi marché ?
+ SUBSET-SUM est évidemment NP.
Pour montrer qu’il est NP-complet nous allons suivre l’indication et effectuer une réduction à partir de 3-SAT. Pour ce faire nous
allons commencer en transformant les données de 3-SAT en chiffres.
Soit C0 , . . . , Cm−1 les clauses et x0 , . . . , xn−1 les variables de 3-SAT. On construit vi et vi0 de la manière suivante :
−1 −1 0
vi = 10m+i + ∑m j 0
j=0 ( bij 10 ) et vi = 10
m +i
+ ∑m j
j=0 ( bij 10 ), 1 ≤ i ≤ n − 1 avec

 
1 si xi apparaît dans Cj 1 si xi apparaît dans Cj
bij = et bij0 =
0 sinon 0 sinon

Pour mieux comprendre ce qu’on fait, on peut imaginer qu’on crée des (m + n)-upplets dont les n premières cases il n’y à que des
zéros sauf à un endroit i qui permet de savoir de quelle variable on parle, que ce soit xi ou xi , et les m suivants permettent de savoir
si la variable est dans les clauses correspondantes.

2
 Entier n variables m clauses Commentaires
xn−1 xn−2 ... x0 Cm−1 Cm−2 ... C0
v0 00 . . . 1 ...1...1... 1 : clauses dans lesquelles x0 apparaît
v n −2 01 . . . 0 ...1... 1 : clauses dans lesquelles xn−2 apparaît
v00 0...1 ...1...1... 1 : clauses dans lesquelles x0 apparaît
vi0 . . . 010 . . . ...1...1... 1 : clauses dans lesquelles xi apparaît
s0 00 . . . 0 00 . . . 1 Uniquement 1 dans colonne C0
si 00 . . . 0 ...1... Uniquement 1 dans colonne Ci
s10 00 . . . 0 00 . . . 02 Uniquement 2 dans colonne C0
si0 00 . . . 0 . . . 020 . . . Uniquement 2 dans colonne Ci
t 11 . . . 1 44 . . . 4 Entier objectif

−1
Désormais on va sommer certains vi et certains vi0 , en fait on somme n entiers, un par littéral, T = ∑nk= 0
0 [ x k vk + (1 − x k ) vk ]. T est
un nombre qui commence par n "1" et est suivit de m chiffres compris entre 0 et 3 (comme on est parti de 3-SAT il y a au plus 3
variables par clause et ces m chiffres correspondent exactement au nombre de littéraux qui mettent cette clause à vrai). Si on part
d’une solution du problème 3-SAT, et qu’on prend vi si xi est vrai et vi0 si xi est faux, on remarque que ces m chiffres sont compris
entre 1 et 3.
A partir de là on se demande comment faire la différence entre les sous-ensembles donnant une somme qui contient un "0" de ceux
donnant une somme sans "0" qui sont exactement les sous-ensembles correspondant à un certificat du problème 3-SAT par la bijection
évidente vi ∈ S’ ↔ xi est vrai et vi0 ∈ S’ ↔ xi est vrai.
C’est à cela que servent les s j = 10 j et s0 j = 2.10 j . En prenant t = 1 . . . 14 . . . 4 et en ne réfléchissant que sur les m chiffres de droite de
T on voit que :
— à partir de 3 on peut avoir 4,3 + 1
— à partir de 2 on peut avoir 4,2 + 2
— à partir de 1 on peut avoir 4,1 + 1 + 2
— à partir de 0 on ne peut avoir 4.
(Cette réflection est la même qui si on considère les nombres comme des n + m-upplets)
Le problème 3-SAT est donc réduit en SUBSET-SUM avec S = {vi |1 ≤ i ≤ n − 1} ∪ {vi0 |1 ≤ i ≤ n − 1} ∪ {s j |1 ≤ j ≤ m − 1} ∪ {s j |1 ≤
j ≤ m − 1} et t = 1 . . . 14 . . . 4
On a ainsi que, si on trouve une solution du problème 3-SAT, on a une solution du problème SUBSET-SUM en prenant la bijection
précédente, et en complétant avec les s j = 10 j et s0 j = 2.10 j .
Réciproquement, si on trouve un sous-ensemble S’ de S tel que si ∑ x∈S0 ( x ) = t = 1 . . . 14 . . . 4, en prenant S̃ = S0 ∩ ({vi |1 ≤ i ≤
n − 1} ∪ {vi0 |1 ≤ i ≤ n − 1}) on a nécessairement T = ∑ x∈S̃ ( x ) qui est nombre commençant par n "1" et suivit de m chiffres compris
entre 1 et 3 (ni 0 ni 4 : au plus 3 peut venir des si et si0 , il y a nécessairement un 1 qui vient des vi ou vi0 ), ce qui montre que comme
aucun "0" n’apparaît, les instances de 3-SAT peuvent toutes êtres mises à vrai, trouvé à l’aide de la bijection citée plus haut, donc à
partir du certificat de ce problème SUBSET-SUM on retrouve un certificat du problème 3-SAT de départ.
La réduction précédente est polynomiale car on passe de n variables et m clauses à 2n + 2m entiers de m chiffres, SUBSET-SUM est donc NP-complet.
+ Remarque : On peut faire le même travail dans toutes les autres bases qui n’introduisent pas de problèmes dus aux phénomènes
de retenue.
+ Remarque : On peut aussi remplacer les "4" dans t par n’importe quel autre chiffre supérieur à 4, à condition de rajouter des "s"
en nombre suffisant.
+ Remarque : On peut aussi faire des s˜i = 10m+i sans changer t, ça remplace les variables pour lesquelles on peut choisir n’importe
que booléen.