Satisfiability of bounded assignment of input variables to CNF formula

Question

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.

Answer 1

The choice of set cover might not be ideal. Let us rephrase the problem. You get a set of $m$ cluases $C_1, \dots C_m$ each consists of negative variables only. You need to find a set of $k$ variables that intersects each of these clauses (the variables that you would assign the value $0$. Clearly this corresponds to the hitting set problem defined as follows:

The hitting set problem

Given a family of $m$ sets $\mathcal{F} = \{S_1, \dots S_m\}$ over a ground set $U$. Is there a set of at most $k$ elements that have a non empty intersection with each of the sets in $\mathcal{F}$.

This problem is also NP-complete.