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 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
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 … 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
