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 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.
Catégories : Algorithmique | Problème NP-complet
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
