Problème 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 une valuation Vrai ou Faux de chaque variable vi, telle 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 de l'existence d'une clique dans un graphe.


Wikimedia Foundation. 2010.

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

Regardez d'autres dictionnaires:

  • Probleme SAT — 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

  • 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

  • Problème 3SAT — 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 …   Wikipédia en Français

  • 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 une formule… …   Wikipédia en Français

  • SAT — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. {{{image}}}   Sigles d une seule lettre   Sigles de deux lettres > Sigles de trois lettres …   Wikipédia en Français

  • Sat — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. {{{image}}}   Sigles d une seule lettre   Sigles de deux lettres > Sigles de trois lettres …   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

  • SAT-Problem — Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von engl. satisfiability) ist ein Entscheidungsproblem. Es fragt, ob eine aussagenlogische Formel erfüllbar ist. Anwendungen finden sich unter anderem in der Komplexitätstheorie, Verifikation und… …   Deutsch Wikipedia

  • Problème P = NP — En mathématiques, et plus précisément en informatique théorique, la relation entre la classe des problèmes de complexité P et la classe des problèmes de complexité NP est un problème non résolu, et est considéré par de nombreux chercheurs comme… …   Wikipédia en Français

  • Sat (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sat est le nom de : Sat, un rappeur français, membre de la Fonky Family. Problème SAT, un problème de décision d une grande importance en théorie de… …   Wikipédia en Français