SAT satisfaction à 10 variables

Question

J'essaie de prouver que le prochain problème est NPC:

$$ A={\ étouffe \ Phi \ RANGER \ \ BIG |\ \ phi \ \ text {est CNF et a SAT.affectation où exactement 10 vars sont true} \} $$

J'essaie de trouver une réduction de cartographie polynomiale de SAT, mais je ne trouve pas un moyen de forcer exactement 10 variables pour obtenir une véritable affectation. Mon idée était de créer une nouvelle formule, avec 10 clauses, chaque clause est l'intersection d'une nouvelle variable $ x_i $ avec l'ancienne formule, mais je ne vois pas commentmon idée utile.

J'apprécierais de l'aide.

Answer 1

Le problème que vous avez mentionné est dans $ p $ donc ce n'est pas NP-complet.Nous savons que $ | \ phi |= n $ donc le nombre de variables est inférieur à $ n $ et nous savons que des membres de $ a$ avoir exactement 10 missions vraies.Donc, par un algorithme de force brute, vérifiez chaque affectation possible aux variables.Choisissez 10 variables de n, $ (^ {n} _ {10}) $ et définissez-les sur $ vrai $ Et définissez d'autres variables sur $ FAUX $ et vérifiez s'il s'agit d'une affectation satisfaisante.Le temps d'exécution de cet algorithme est $ (^ {n} _ {10}) * n= o (n ^ {11}) $ .

.