Consider a CNF formula F = C1 C2 Cm where every
Question:
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.
Analysis and Design of Analog Integrated Circuits
ISBN: 978-0470245996
5th edition
Authors: Paul R. Gray,? Paul J. Hurst Stephen H. Lewis,? Robert G. Meyer