# Satisfiability of bounded assignment of input variables to CNF formula

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.

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:
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}$$.