3-SAT

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:

  • SAT-Amikaro — Contexte général Champs d’action Mettre l espéranto plus particulièrement au service des personnes pour lesquelles cette langue présente en premier lieu un intérêt d ordre social, pédagogique, culturel et pratique Zone …   Wikipédia en Français

  • SAT Amikaro — Contexte général Champs d action Mettre l espéranto plus particulièrement au service des personnes pour lesquelles cette langue présente en premier lieu un intérêt d ordre social …   Wikipédia en Français

  • Sat-amikaro — Contexte général Champs d action Mettre l espéranto plus particulièrement au service des personnes pour lesquelles cette langue présente en premier lieu un intérêt d ordre social …   Wikipédia en Français

  • Sat l'Artificier — Sat, en studio pour le 2ème album solo. (Aubagne). Nom Karim Haddouche Naissance 16 septembre 1975 …   Wikipédia en Français

  • SAT-3/WASC (cable system) — SAT 3/WASC or South Atlantic 3/West Africa Submarine Cable is a submarine communications cable linking Portugal and Spain to South Africa, with connections to several West African countries along the route. It forms part of the SAT 3/WASC/SAFE… …   Wikipedia

  • Sat-Yr-9 — Sat Yr 9. Art by Alan Davis Publication information Publisher Marvel Comics/Marvel UK …   Wikipedia

  • Sat.1 Österreich — Senderlogo Ehemaliges Logo Allgemeine Informationen Empfang …   Deutsch Wikipedia

  • sat — SAT, sate, s.n. 1. Aşezare rurală a cărei populaţie se ocupă în cea mai mare parte cu agricultura. ♢ expr. Satul lui Cremene sau sat fără câini = loc fără stăpân, fără control, în care oricine poate face ce doreşte. 2. Locuitorii dintr un sat… …   Dicționar Român

  • Sat — ist ein Begriff im Hinduismus, siehe Sat Chit Ananda Die Abkürzung SAT steht für: Satellit, davon abgeleitet auch für: Satellitenfernsehen; Satellitenreceiver; SAT Anlage; SAT Kopfstelle. Körperschaften (Institutionen, Organisationen): SAT… …   Deutsch Wikipedia

  • Sat.1 Comedy — Senderlogo Allgemeine Informationen Empfang: Kabel …   Deutsch Wikipedia

  • SAT en Hispanio — SAT en Espagne SAT en Hispanio Contexte général Champs d action Information concernant l espéranto auprès des travailleurs …   Wikipédia en Français

Share the article and excerpts

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