2
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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