Return to Revisions

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