Consider a CNF formula $F$ such that all the literals in every clause must be negative ( here is an example : $F$ = ($\bar{x_{1}}$ $\wedge$ $\bar{x_{2}}$) $\vee$ ($\bar{x_{3}}$ $\wedge$ $\bar{x_{4}}$ $\wedge$ $\bar{x_{5}}$) would be a valid formula where as $F$ = ($x_{1}$ $\vee$ $\bar{x_{3}}$ ) would not be a valid formula $F$ . It is known that this type of formula is satisfiable given you can set every variable to 0 , which will satisfy all the clauses . However, what if you received a positive integer $i$ and were asked if you could assign at most $i$ variables to a value of 0.
I know $F$ would still be satisfiable, and I know this would be NP-Complete. However, I am having difficulty reducing set cover to this problem in order to prove NP-completeness. I know that there being negations everywhere would result in the same number ( but inverted ) of truth assignments that would lead to satisfiability compared to if there were not any in the first place. Maybe trying to reduce set-cover to this problem is a dead end? Let me know what you think.