Problème 3-SAT

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis 3-SAT)
Aller à : navigation, rechercher

Le problème 3-SAT est un problème d'informatique théorique surtout étudié du point de vue de la théorie de la complexité des algorithmes.

Description[modifier | modifier le code]

Il s'agit de la restriction du problème SAT aux formes normales conjonctives avec au plus 3 littéraux (ou exactement 3 selon les sources[1]). C'est l'un des 21 problèmes NP-complets de Karp.

Exemple[modifier | modifier le code]

Un exemple d'instance de ce problème :

a 4 clauses, 5 littéraux et trois littéraux par clauses.

Résoudre cette instance de ce problème revient à déterminer s'il existe une valuation Vrai ou Faux de chaque variable telle que soit Vrai.

Utilisation pour les preuves de NP-complétude[modifier | modifier le code]

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.

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Pour « au plus 3 », voir (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 2.3 (« The Cook-Levin Theorem: Computation is Local ») p. 43.