Consider a CNF formula F = C1 ∧ C2 ∧ · · · ∧ Cm where every boolean literal occurring in F is [10] negative. So, for example, F = (x1∨x2)∧(x3∨x4∨x1) is such a formula, but F = x1∧(x2∨x4) is not. It is easy to see that such a formula F is always satisfiable, since setting xi = 0 for every I will satisfy all the clauses. However, we will show that it is hard to find satisfying assignments where we only set a bounded number of input variables to 0. Formally, consider the following problem. As input, you receive a CNF formula F where every boolean literal in F is negative and a positive integer k. The goal is to decide if there is a satisfying assignment x to the variables of F such that at most k input variables are assigned to 0.

Prove that this problem is NP-Complete.