[Solved]: Monotone boolean satisfiability with at most k 1s is NP-Complete

Problem Detail: 

I am to prove that monotone boolean formula satisfiability checking when at most k variables are set to 1 is an NP-Complete problem. Proving that it is in NP is easy, but I'm having difficulty showing that it is in NP-Hard. I have seen this, but I would rather not use its solution, as the textbook for the course I am self studying does not present Dominating Sets as an NP-Complete problem. The NP-Complete problems presented in my book(Dasgupta, Papadimitriou, and Vazirani) are the following: 3SAT, Traveling Salesman, Longest Path, 3D-Matching, Knapsack, Independent Set (related to Dominating Set from what I understand), Vertex Cover, Clique, Integer Linear Programming, Rudrata Path, and Balanced Cut.

From my understanding of the problem, if you restrict the clauses to 2 literals each, then this directly parallels the vertex cover problem, and is thus NP-hard. I was wondering if there was any way that I could use this fact to say that the unrestricted problem is also NP-Hard. I intuitively feel that this should work, because the restricted version is a subset of the restricted version, so in at least some cases the problem is NP-hard. Since you always take the worst case scenario, could you extend this to NP-hardness for the unrestricted problem? If so, how would I word that (this is for a self study, not to be turned in), in the proper form? Because my above explanation has a roundabout method of showing the point.

tl;dr Can you prove that something is np-hard by showing that a subproblem is np-hard? I intuitively feel like you should, but want to confirm.

Asked By : Nezo

Answered By : Yuval Filmus

Let $L'$ be a restriction of $L$, say $L' = L \cap D$. Here $D$ is a restriction on the inputs such as "all clauses have two literals each".

Suppose that $L'$ is NP-hard. Then for every language $M$ in NP, there is a polytime reduction $\varphi$ from $M$ to $L'$ such that $x \in M$ iff $\varphi(x) \in L'$. If $\varphi(x) \in D$ for all $x$, then $\varphi(x) \in L'$ iff $\varphi(x) \in L$, and so $\varphi$ is also a reduction from $M$ to $L$.

Usually NP-hardness proofs go by reduction from some specific NP-complete problem $M$. If the polytime reduction $\varphi$ from $M$ to $L'$ showing that $L'$ is NP-hard satisfies the property $\varphi(x) \in D$ for all $x$ (in other words, its range is [contained in] $D$), then the reasoning in the preceding paragraph shows that $\varphi$ also proves that $L$ itself is NP-hard.

For example, in your case $L$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone Boolean formula that can be satisfies by setting at most $k$ of the literals to TRUE; $D$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone 2CNF; and $L' = L \cap D$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone 2CNF that can be satisfied by setting at most $k$ of the literals to TRUE. Any reduction $\varphi$ showing that $L'$ is NP-complete whose range is $D$ also shows that $L$ is NP-complete.

To check that you understand the argument, try to see what goes wrong when we take $L'$ to be, say, 3SAT, and $L$ to be the language of all 3CNFs.

Finally, here is a trick that you can use to emulate SAT in your setting. Suppose that some CNF $\varphi$ has variables $x_1,\ldots,x_n$, some of them possibly appearing negated. Consider $\psi = \varphi' \land (x_1 \lor y_1) \land \cdots \land (x_n \lor y_n)$, where $\varphi'$ results from replacing $\lnot x_i$ by $y_i$. Then $\varphi$ is satisfiable iff $\psi$ is satisfiable by a truth assignment in which at most (or exactly) $n$ variables are TRUE.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28274