3-sat vers clique
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
[modifier] réduction polynomiale
Pour réduire le problème 3-SAT vers celui de la clique, à chaque formule 3-CNF, on associe un graphe non orienté dont le nombre de sommets est 3 fois le nombre de clauses de la manière suivante: à chacun des trois littéraux de chaque clause, on associe un sommet; on relie les sommets par des arêtes de la manière suivante : deux sommets qui sont associés aux littéraux d'une même clause ne sont pas reliés par une arête, et deux sommets qui sont associés à un littéral et sa négation ne sont pas reliés non plus, tous les autres couples de sommets sont reliés.
On démontre alors que la formule à k clauses est satisfiable si et seulement si le graphe a une clique d'ordre k.
Idée de la preuve:
Si la formule est satisfiable, il existe une assignation des variables pour laquelle la valeur d'au moins un littéral de chaque clause est VRAI. L'ensemble formé des sommets associés à l'un de ces littéraux par clause est une clique du graphe.
Si le graphe a une clique d'ordre k, elle contient exactement un sommet parmi les trois qui représentent les littéraux de chaque clause; on peut définir une assignation des variables pour laquelle la valeur de ces littéraux est VRAI; la valeur de la formule pour cette assignation est alors VRAI.
|
Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques. |
