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?

$\endgroup$
  • $\begingroup$ You are probably interested in a satisfying assignment. $\endgroup$ – Yuval Filmus Oct 17 at 20:17
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).

$\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.