3-SAT

Problème 3-SAT

Le problème 3-SAT est un cas particulier du problème SAT quand la taille des clauses est exactement de 3. C'est l'un des 21 problèmes NP-complets de Karp.

Un exemple d'instance de ce problème :

E=(v_1 \lor v_2 \lor v_3) \land (\neg v_1 \lor v_2 \lor v_4) \land (\neg v_1 \lor v_2 \lor \neg v_5) \land (\neg v_3 \lor v_4 \lor v_5)

E a 4 clauses, 5 littéraux v1,v2,v3,v4,v5 et trois littéraux par clauses.

Pour résoudre cette instance de ce problème il faut trouver un assignement (Vrai ou Faux) pour chaque variable tel que E soit Vrai.

Comme 3-SAT est NP-complet et SAT est réductible à ce problème, 3-SAT est utilisé pour prouver que d'autres problèmes sont NP-complet. Par exemple cette méthode a été utilisée pour le problème d'une clique dans un graphe.

Ce document provient de « Probl%C3%A8me 3-SAT ».

Wikimedia Foundation. 2010.

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

Regardez d'autres dictionnaires:

  • 3-SAT — ist eine Variante des Erfüllbarkeitsproblems der Aussagenlogik (Erfüllbarkeit engl.: satisfiability, kurz SAT). Es beschäftigt sich mit der Frage, ob eine in konjunktiver Normalform vorliegende aussagenlogische Formel F, die höchstens 3 Literale… …   Deutsch Wikipedia

  • 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

  • 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

  • France 3 sat — Création 16 décembre 1996 Slogan « De près, on se comprend mieux » Langue Français Pays d origine …   Wikipédia en Français

  • France 3 Sat —  Pour la chaîne germanophone, voir 3sat. Création 16 décembre 1996 Slogan De près, on se comprend m …   Wikipédia en Français

  • France 3 Sat — Страна …   Википедия

  • Problème 3-SAT — Le problème 3 SAT est un cas particulier du problème SAT quand la taille des clauses est exactement de 3. C est l un des 21 problèmes NP complets de Karp. Un exemple d instance de ce problème : E a 4 clauses, 5 littéraux v1,v2,v3,v4,v5 et… …   Wikipédia en Français

  • Sat Nam — is a frequently used mantra for meditation exercises and has become popularized by Kundalini yoga instructors. It is also used in Surat Shabd Yoga [http://santhakar.tripod.com/teachers/mast 1.htm] and, within Eckankar… …   Wikipedia

  • SAT (problème) — Problème SAT On nomme problème SAT un problème de décision visant à savoir s il existe une solution à une série d équations logiques données. En termes plus précis : une valuation sur un ensemble de variables propositionnelles[1] telle qu… …   Wikipédia en Français

Share the article and excerpts

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