# SAT satisfaction with 10 variables

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.

• this problem is in P with with an algorithm of $n^{10}$ – Mohsen Ghorbani Jul 29 '20 at 8:14
• Thanks. I just checked that and I understand. thank you:) – Ella Jul 29 '20 at 8:28

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})$$.