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
