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.

  • 5
    $\begingroup$ this problem is in P with with an algorithm of $n^{10}$ $\endgroup$ Commented Jul 29, 2020 at 8:14
  • $\begingroup$ Thanks. I just checked that and I understand. thank you:) $\endgroup$
    – Ella
    Commented Jul 29, 2020 at 8:28

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.