<p>This problem is indeed NP-complete.</p>

<p>Actually, the answer for this question is answered in: </p>

<p><a href="https://cs.stackexchange.com/questions/11558/prove-np-completeness-of-deciding-satisfiability-of-monotone-boolean-formula">https://cs.stackexchange.com/questions/11558/prove-np-completeness-of-deciding-satisfiability-of-monotone-boolean-formula</a></p>

<p>Therefore, this question is closed and answered...</p>

CC BY-SA 4.0
2018-06-15T18:11:28.790Z
2018-06-15T18:11:28.790Z
Frank Vega
<p>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?</p>

CC BY-SA 4.0
2018-06-07T21:42:57.127Z
This is answered in: https://cs.stackexchange.com/questions/11558/prove-np-completeness-of-deciding-satisfiability-of-monotone-boolean-formula and is NP-complete...
Frank Vega
CC BY-SA 4.0
2018-06-08T00:21:41.077Z
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? :)
Antoine Amarilli 'a3nm'
<cc.complexity-theory><sat><np-complete><polynomial-time>
Can MONOTONE WSAT be in solved in polynomial time?
Frank Vega
# Can MONOTONE WSAT be in solved in polynomial time?

(Asked by: username_0 on 2018-06-07)

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?

**Tags:** cc.complexity-theory, sat, np-complete, polynomial-time

> **Comments:**
> **username_0**: This is answered in: https://cs.stackexchange.com/questions/11558/prove-np-completeness-of-deciding-satisfiability-of-monotone-boolean-formula and is NP-complete...  
> **username_1**: 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? :)  

---

## 1 answers

### Answer by username_0 on 2018-06-15. Score: 1 | Accepted answer

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


---

