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?

  • 4
    $\begingroup$ This is answered in: cs.stackexchange.com/questions/11558/… and is NP-complete... $\endgroup$
    – Frank Vega
    Commented Jun 7, 2018 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
    Commented Jun 8, 2018 at 0:21

1 Answer 1


This problem is indeed NP-complete.

Actually, the answer for this question is answered in:


Therefore, this question is closed and answered...


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.