SAT satisfaction with 10 variables

Question

I am trying to prove that the next problem is NPC:

$$ A = \{ \langle\phi\rangle \ \big| \ \phi \ \text{is CNF and has sat. assignment where exactly 10 vars are TRUE} \} $$

I am trying to find polynomial mapping reduction from SAT but I can't find a way to force exactly 10 variables to get TRUE assignment. My idea was to create new formula, with 10 clauses, each clause is the intersection of a new variable $x_i$ with the old formula, but I don't see how my idea helpful.

I would appreciate help.

Answer 1

The problem you mentioned is in $P$ so it is not NP-complete. We know that $|\phi| = n$ so the number of variables is less than $n$ and we know that members of $A$ exactly have 10 True assignments. So by a brute force algorithm check every possible assignment to variables. Choose 10 variables from n, $(^{n}_{10})$ and set them to $True$ and set other variables to $False$ and check if this is a satisfying assignment. The run time of this algorithm is $(^{n}_{10})*n = O(n^{11})$.