Prove NP-completeness of deciding satisfiability of monotone boolean formula - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T13:50:10Z https://cs.stackexchange.com/feeds/question/11558 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/11558 12 Prove NP-completeness of deciding satisfiability of monotone boolean formula nat https://cs.stackexchange.com/users/7901 2013-04-25T23:58:57Z 2016-12-11T01:24:39Z <p>I am trying to solve this problem and I am really struggling.</p> <p>A <em>monotone boolean formula</em> is a formula in propositional logic where all the literals are positive. For example, </p> <p>$\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5)$ </p> <p>is a monotone boolean function. On the other hand, something like</p> <p>$\qquad (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor x_3) \land (\neg x_1 \lor x_5)$ </p> <p>is not a monotone boolean function.</p> <p>How can I prove NP-completeness for this problem: </p> <blockquote> <p>Determine whether a monotone boolean function is satisfiable if $k$ variables or fewer are set to $1$? </p> </blockquote> <p>Clearly, all the variables could just be set to be positive, and that's trivial, so that is why there is the restraint of $k$ positively set variables.</p> <p>I have tried a reduction from SAT to monotone boolean formula. One thing I have tried is to substitute a dummy variable in for every negative literal. For example, I tried replacing $\neg x_1$ with $z_1$, and then I tried forcing $x_1$ and $z_1$ to be different values. I haven't quite been able to get this to work though.</p> https://cs.stackexchange.com/questions/11558/-/11559#11559 12 Answer by Luke Mathieson for Prove NP-completeness of deciding satisfiability of monotone boolean formula Luke Mathieson https://cs.stackexchange.com/users/1636 2013-04-26T00:29:58Z 2013-04-26T00:29:58Z <p>The "parent" of the problem you're looking at is sometimes called Weighted Satisfiability (WSAT, particularly in parameterized complexity) or Min-Ones (though this is normally an optimization version, but near enough). These problems have the "at most $k$ variables set to true" restriction as their defining feature.</p> <p>The restriction to monotone formulae is actually surprisingly easy to show hardness for, you just need to thing outside satisfiability problems for a moment. Instead of trying to modify a SAT instance, we instead start with Dominating Set (DS).</p> <p>See if you can get it from there. More is in the spoilers, broken into bits, but avoid them if you can. I won't show membership in NP, you should have no problem with that.</p> <p>The basic construction:</p> <p>A sketch of the proof:</p> https://cs.stackexchange.com/questions/11558/-/67221#67221 2 Answer by david for Prove NP-completeness of deciding satisfiability of monotone boolean formula david https://cs.stackexchange.com/users/62890 2016-12-11T01:24:39Z 2016-12-11T01:24:39Z <p>There is a simple reduction from SAT. Introduce a new variable $z_i$ to represent $\neg x_i$. Given a formula $\phi$, we create a new formula $\phi'$ by replacing each occurrence of $\neg x_i$ with $z_i$, and adding the clause $x_i \vee z_i$ for each variable. We set $k$ to be the number of original variables. The new formula $\phi'$ is monotone, and is satisfiable with at most k variables set to true if and only if $\phi$ is satisfiable. (This is because the $k$ disjoint clauses $x_i \vee z_i$ causes any satisfying assigment for $\phi'$ to have at least $k$ variables to True; but then the only way to have at most $k$ is to have exactly one of them set to true for each pair {x_i, z_i}.)</p>