Problème 3SAT

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=(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 Problème 3SAT de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Probleme du nombre domatique — Problème du nombre domatique Le problème du nombre domatique est un problème NP complet de la théorie des graphes. Définition Une instance du problème du nombre domatique consiste en un graphe G avec un ensemble S de sommets et un ensemble A d… …   Wikipédia en Français

  • Problème du nombre domatique — Le problème du nombre domatique est un problème NP complet de la théorie des graphes. Définition Une instance du problème du nombre domatique consiste en un graphe G avec un ensemble S de sommets et un ensemble A d arcs, et un entier positif k… …   Wikipédia en Français

  • 3sat —  Ne doit pas être confondu avec Problème 3 SAT. Création 1er&# …   Wikipédia en Français

  • Drei letzte Probleme — Die großen Nordwände der Alpen (auch: Klassische Nordwände oder Letzte Probleme der Alpen) sind eine Gruppe von drei oder sechs Nordwänden alpiner Berge, die sich durch ihre besondere Größe, Schwierigkeit oder Gefährlichkeit für Bergsteiger… …   Deutsch Wikipedia

  • Letzte Probleme der Alpen — Die großen Nordwände der Alpen (auch: Klassische Nordwände oder Letzte Probleme der Alpen) sind eine Gruppe von drei oder sechs Nordwänden alpiner Berge, die sich durch ihre besondere Größe, Schwierigkeit oder Gefährlichkeit für Bergsteiger… …   Deutsch Wikipedia

  • Letzte drei Probleme — Die großen Nordwände der Alpen (auch: Klassische Nordwände oder Letzte Probleme der Alpen) sind eine Gruppe von drei oder sechs Nordwänden alpiner Berge, die sich durch ihre besondere Größe, Schwierigkeit oder Gefährlichkeit für Bergsteiger… …   Deutsch Wikipedia

  • Theorie zur Lösung erfinderischer Probleme — TRIZ ist das russische Akronym für теория решения изобретательских задач (Teoria reshenija izobretatjelskich zadacz), was sinngemäß übersetzt bedeutet: Theorie des erfinderischen Problemlösens oder Theorie zur Lösung erfinderischer Probleme .… …   Deutsch Wikipedia

  • Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La …   Wikipédia en Français

  • Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • Liste de problemes NP-complets — Liste de problèmes NP complets Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets,… …   Wikipédia en Français

Share the article and excerpts

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