Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Problème SAT

Le problème SAT est un problème de décision d'une grande importance en théorie de la complexité.

Le problème SAT s'énonce de la manière suivante :

• Données : une formule logique F de m clauses sur n variables.
• Question : F est elle satisfiable ? – c'est-à-dire, existe-t-il une façon d'assigner les valeurs « vrai » ou « faux » aux variables afin de rendre la formule vraie ?

SAT est un problème NP-complet.

On obtient de même un problème NP-complet si on se restreint au problème 3SAT : étant donné une formule logique de la forme (u₁∨v₁∨w₁) ∧ ... ∧ (u_m∨v_m∨w_m), avec les u_i, u_v, u_w choisis dans un ensemble de n variables et de leurs négations.