3-SAT vers clique

Le 3-SAT vers clique est une question de logique mathématique.

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 trois 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, 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.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article 3-SAT vers clique de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • 3-sat vers clique — Le 3 SAT vers clique est une question de logique mathématique. 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 trois fois le… …   Wikipédia en Français

  • 3 sat vers clique — Le 3 SAT vers clique est une question de logique mathématique. 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 trois fois le… …   Wikipédia en Français

  • Sapienti sat — − Geflügelte Worte   A B C D E F G H I J K L M N O …   Deutsch Wikipedia

  • Reduction polynomiale — Réduction polynomiale Sommaire 1 Définition 2 Relation entre un problème de décision et son langage associé 2.1 Codage 2.2 …   Wikipédia en Français

  • Réduction polynomiale — Sommaire 1 Définition 2 Relation entre un problème de décision et son langage associé 2.1 Codage 2.2 R …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Problème NP-complet — En théorie de la complexité, un problème NP complet est un problème de décision vérifiant les propriétés suivantes : Il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette… …   Wikipédia en Français

  • Virgin 17 — Création 17 octobre 2005 Disparition 1er septembre 2010 Propriétaire Groupe MCM …   Wikipédia en Français

  • Liste geflügelter Worte/S — Geflügelte Worte   A B C D E F G H I J K L M N O P Q R S T U V W Y Z Inhaltsverzeichnis …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”