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?

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

1 Answer 1

Reset to default
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...

Improve this answer
$\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.