1
$\begingroup$

Given a 2SAT instance in CNF where each clause has at most two literals. Let $m$ be the number of clauses and $n$ be the number of variables et let $k$ be a positive number.

Question: Is there a truth assignment such that the number of variables that are true is $k$ or more?

I cannot find the name of this problem, if it was already studied? If so, is it NP-hard?

Improve this question
$\endgroup$
1
  • $\begingroup$ You are probably interested in a satisfying assignment. $\endgroup$
    – Yuval Filmus
    Oct 17, 2019 at 20:17

1 Answer 1

Reset to default
4
$\begingroup$

Your problem is known as Weighted-2-satisfiability, and is known to be NP-complete. The easiest way to see that is by reduction from Vertex Cover (exercise).

Note that the link above is about whether there is a satisfying assignment having at most $k$ true variables. This is equivalent to your problem (exercise).

Improve this answer
$\endgroup$

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.