Corrigé Centrale 2025 Informatique MPI — Partie B, II (réduction) (Q33 à Q38) : Réduction de Planar 3SAT à 3CASSE : gadgets et NP-complétude

Les quatre gadgets ont été vérifiés par énumération exhaustive (Python) de tous les ensembles de camions disjoints qu'ils peuvent porter ; le terrain de Q37 a été traité par une recherche exhaustive avec élagage, qui confirme le maximum annoncé et la disposition proposée.

Deux remarques servent partout. (i) Un camion qui appartient à un gadget couvre trois cases de ce gadget ; une case d'un gadget qui n'est partagée avec aucun autre ne peut être couverte que par un camion du gadget lui-même. (ii) Un signal $e$ vrai pour $\epsilon$ signifie que la case $e$ est libre ou couverte par un camion de $\epsilon$ ; si $\epsilon$ couvre $e$, ce camion n'appartient pas au gadget voisin qui partage $e$, et le signal $e$ est faux pour ce voisin. « Rendre $b$ faux pour le gadget suivant », c'est donc poser un camion du gadget sur $b$.

Q33. Numérotons les cases de la ligne de $0$ à $4$ de gauche à droite ($a$ en $1$, $b$ en $3$), la colonne descendant de la case $2$ vers $c$. Il n'y a que quatre positions de camion dans ce gadget : dans la ligne, sur les cases $\{0,1,2\}$, $\{1,2,3\}$ ou $\{2,3,4\}$ ; dans la colonne, sur la case $2$, la case du milieu et $c$ (la colonne n'a que trois cases, et aucune autre droite ne contient trois cases du gadget). Les quatre contiennent la case $2$ de la ligne : deux camions du gadget se chevaucheraient, donc il en accueille $0$ ou $1$. Chaque position contient $a$, $b$ ou $c$ (respectivement $a$ ; $a$ et $b$ ; $b$ ; $c$). Si les trois signaux sont faux, ces trois cases sont occupées par des camions étrangers et aucune position n'est libre : aucun camion. Si $a$ est vrai, la case $a$ est libre (un camion du gadget est exclu, puisqu'on n'en a posé aucun), les cases $0$ et $2$ ne sont partagées avec aucun gadget et sont libres par (i) : on pose le camion $\{0,1,2\}$. De même $\{2,3,4\}$ si $b$ est vrai, et la colonne si $c$ est vrai. Le gadget accueille un camion si et seulement si l'un des signaux est vrai (vérifié pour les $8$ combinaisons de signaux).

Q34. Les cases sont numérotées $0$ ($a$) à $6$ ($b$) ; les positions sont les cinq triplets $\{k,k+1,k+2\}$, $0⩽k⩽4$. Si $a$ est faux, deux camions du gadget, disjoints, tiennent dans les six cases $1$ à $6$ : ils les remplissent exactement, et ce sont nécessairement $\{1,2,3\}$ et $\{4,5,6\}$. La case $b$ est couverte : $b$ devient faux pour le gadget suivant. Si $a$ est vrai, on pose $\{0,1,2\}$ et $\{3,4,5\}$ : la case $b$ reste libre, et $b$ reste vrai pour le gadget suivant (s'il n'y pose pas lui-même de camion, il n'y a aucune protrusion). L'énumération confirme : avec $a$ faux, un seul placement de deux camions, et il couvre $b$.

Q35. Les cases sont : la rangée du haut $h_1,h_2,h_3,b$ (de gauche à droite), la case $m$ sous $h_1$, la rangée du bas $g,m^{\prime },a$ avec $m^{\prime }$ sous $m$. Les seules positions sont $\{h_1,h_2,h_3\}$, $\{h_2,h_3,b\}$, la colonne $\{h_1,m,m^{\prime }\}$ et la rangée $\{g,m^{\prime },a\}$. Si $a$ est faux, la rangée du bas est exclue, donc $g$ reste libre ; deux camions doivent remplir les six cases restantes $h_1,h_2,h_3,b,m,m^{\prime }$. La case $m^{\prime }$ n'est plus couverte que par la colonne ; elle est donc posée, et le second camion, disjoint d'elle, ne peut être que $\{h_2,h_3,b\}$ : $b$ est couverte, faux pour le gadget suivant. Si $a$ est vrai, on pose $\{g,m^{\prime },a\}$ et $\{h_1,h_2,h_3\}$, disjoints, et $b$ reste libre, donc vrai. Le gadget décale le signal de deux cases : avec les transmissions de Q34 (décalages multiples de $3$), on obtient tout décalage, $2\times 2=4\equiv 1(\mathrm{mod}3)$.

Q36. Le gadget a $17$ cases : deux bras en équerre, à gauche $b$, trois cases de la rangée du haut et la colonne qui descend sous la troisième ; à droite le symétrique jusqu'à $c$ ; entre les deux colonnes, la colonne centrale, deux cases au-dessus de $a$. Les deux rangées basses du bloc $2\times 3$ (colonne gauche, colonne centrale, colonne droite) sont notées $R_1$ (haut) et $R_2$ (bas). Les $11$ positions possibles sont : deux dans chaque demi-rangée du haut, deux dans chacune des deux colonnes latérales (de quatre cases, de la rangée du haut à $R_2$), la colonne centrale avec $a$, et les deux rangées $R_1$, $R_2$.