3-SAT 3-COLORING | NP COMPLETUDE
Correction NP COMPLÉTUDE
- Démonstration : La coloration à trois couleurs est un problème qui appartient à la classe NP.
- Certificat : Pour chaque nœud, une couleur choisie parmi {1, 2, 3}.
- Certifier : Vérification que pour chaque arête (u, v), la couleur du nœud u est différente de celle du nœud v.
- Difficulté : Nous allons démontrer que le problème 3-SAT est réductible au problème de coloration à trois couleurs (3-Coloration). 3-SAT ≤P 3-Coloring
Nous débutons avec une formule 3-SAT φ qui possède n variables x1, ..., xn et m clauses C1, ..., Cm. Nous créons le graphe Gφ de telle manière que Gφ soit colorable à trois couleurs si et seulement si φ est satisfaisable.
- Il nous faut établir une attribution de vérité pour x1, ..., xn en utilisant les couleurs pour certains nœuds de Gφ.
- Nous créons un triangle avec les nœuds Vrai, Faux et Base.
- Pour chaque variable xi, nous avons deux nœuds vi et ¬vi reliés par une arête dans un triangle partageant le nœud Base.
- Si le graphe peut être coloré à trois couleurs, soit vi soit ¬vi doit obtenir la même couleur que Vrai. Nous interprétons ceci comme une attribution de vérité à vi.
- Pour chaque clause Cj = (a ∨ b ∨ c), nous créons un petit graphe gadget. Le graphe gadget est relié aux nœuds correspondant à a, b, c. Cela doit implémenter la fonction OU (OR).
Propriété : Si a, b, c sont colorés Faux dans une coloration à trois couleurs, alors le nœud de sortie du gadget OR doit être coloré Faux.
Propriété : Si l'un parmi a, b, c est coloré Vrai, alors le gadget OR peut être coloré à trois couleurs de telle manière que la sortie du gadget OR soit colorée Vrai.
Nous créons un triangle avec les nœuds Vrai, Faux et Base.
- Pour chaque variable xi, nous avons deux nœuds vi et ¬vi reliés par une arête dans un triangle partageant le nœud Base.
- Pour chaque clause Cj = (a ∨ b ∨ c), nous ajoutons le graphe gadget OR avec les nœuds d'entrée a, b, c et nous relions le nœud de sortie du gadget à la fois au nœud Faux et au nœud Base.
Exemple φ = (u ∨ ¬v ∨ w) ∧ (v ∨ x ∨ ¬y)
Si φ est satisfaisable, alors cela implique que Gφ est 3-Coloriable .
- Si xi est attribué Vrai, nous colorons vi en Vrai et ¬vi en Faux.
- Pour chaque clause Cj = (a ∨ b ∨ c), au moins l'un parmi a, b, c doit être coloré Vrai. Le gadget OR pour Cj peut être coloré à trois couleurs de manière à ce que la sortie soit colorée Vrai.
Si Gφ est 3-Coloriable , alors φ est satisfaisable.
- Si vi est coloré Vrai, nous attribuons Vrai à xi, ce qui constitue une attribution de vérité valide.
- Pour toute clause Cj = (a ∨ b ∨ c), il ne peut pas être que a, b, c soient tous colorés Faux. Si tel était le cas, la sortie du gadget OR pour Cj doit être colorée Faux, mais cette sortie est reliée à la Base et à Faux !
Ajouter un commentaire