1
$\begingroup$

In the weighted monotone satisfiability problem (MONOTONE WSAT), the input is an n-variable MONOTONE CNF Boolean formula (when there is no a clause with a negated variable) and an integer k, and the problem is to decide whether there exists a satisfying assignment in which at most k of the variables are true. Can MONOTONE WSAT be in solved in polynomial time or is also NP-complete?

$\endgroup$
  • 4
    $\begingroup$ This is answered in: cs.stackexchange.com/questions/11558/… and is NP-complete... $\endgroup$ – Frank Vega Jun 7 '18 at 21:42
  • 3
    $\begingroup$ Thanks! As this answers your question, could you consider posting it as an answer and accepting it, so that it is clear to everyone that your question is answered? :) $\endgroup$ – a3nm Jun 8 '18 at 0:21
1
$\begingroup$

This problem is indeed NP-complete.

Actually, the answer for this question is answered in:

https://cs.stackexchange.com/questions/11558/prove-np-completeness-of-deciding-satisfiability-of-monotone-boolean-formula

Therefore, this question is closed and answered...

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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