L'Atelier Monstre

Définitoin du problème SAT SAT signifie Satisfaisabilité. Le problème k-SAT consiste à déterminer si une formule booléenne composée de m clauses, chacune contenant exactement k littéraux (variables ou leur négation), est satisfaisable. Pour k ≥ 3, il a été prouvé que k-SAT est NP-complet. Cependant, le cas particulier 2-SAT (où chaque clause co ...