Skip to main content

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$$x_i \lor 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$k$ variables set to true if and only if $\phi$ is satisfiable. (This is because the $k$ disjoint clauses $x_i \vee z_i$$x_i \lor z_i$ causes any satisfying assigmentassignment for $\phi'$ to have at least $k$ variables to True;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}$\{x_i, z_i\}$.)

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

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 \lor 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 \lor z_i$ causes any satisfying assignment 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\}$.)

Source Link
david
  • 151
  • 1
  • 1

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