# Prove that this language is NP-Hard

Given
$$\mathrm{\#3SAT} = \{ (w, y) \mid w\text{ is a \mathrm{3SAT} instance with at least y satisfying assignments}\}\,,$$ prove that $$\mathrm{\#3SAT}$$ is NP-Hard.

I am currently stuck with this one.

Basically $$\mathrm{\#3SAT}$$ is the counting version of $$\mathrm{3SAT}$$ and to me it is seems clear that establishing membership in the language is more complex than establish the classic $$\mathrm{3SAT}$$ membership.

I'm trying to reason through the prover-verifier paradigm: let's say you have a $$\mathrm{3SAT}$$ instance, now suppose the certificate for that instance is $$n$$ bits. It is obvious that the certificate for the same instance but translated into $$\mathrm{\#3SAT}$$ with let's say $$y=10$$ would be at least $$10n$$ bits. So if the first can be examined in time $$t$$ then the second will take at least $$10t$$ and so on. However I am not satisfied with this reasoning, it seems incomplete and superficial. I would greatly appreciate your advice on how to proceed with this proof. Thanks in advance.

It seems that you're trying to prove that $$\#\mathrm{3SAT}$$ is in $$\mathrm{NP}$$. Since $$\#\mathrm{3SAT}$$ is $$\mathrm{\#P}$$-complete, and $$\mathrm{\#P}$$ seems to be harder than anything in the polynomial hierarchy, it's very unlikely that $$\#\mathrm{3SAT}\in\mathrm{NP}$$.

The error in your attempted proof is that your certificate doesn't have polynomial length. A satisfying assignment has length $$\Theta(|x|)$$ (the formula can't have more variables than its length, but it could be of the form $$(x_1\lor x_2\lor x_3) \land (x_4\lor x_5\lor x_6) \land\dots$$). The number $$y$$ could have any value between zero and $$2^{|y|}-1$$, so your certificate has length about $$|x|2^{|y|}$$, which is exponential in the input size.

However, the question asks you to prove that it's $$\mathrm{NP}$$-hard, not that it's $$\mathrm{NP}$$-complete. You just need to prove that there's a polynomial-time reduction from some $$\mathrm{NP}$$-complete problem to $$\#\mathrm{3SAT}$$.

• thanks for the answer. What about this sketch: a NTM can decide membership to 3SAT in polynomial time. Then to decide membership in #3SAT it will take a polynomial expansion on the time implied to decide 3SAT. – Yamar69 Jun 17 at 10:02
• @Yamar69 You're supposed to be reducing problems to $\mathrm{\#3SAT}$, not designing algorithms for $\mathrm{\#3SAT}$. – David Richerby Jun 17 at 10:07
• David Richerby i know but that is the hard part for me :( can you give me a direction? – Yamar69 Jun 17 at 10:11
• Not being rude, but I'm not sure you do know. You started off trying to prove $\mathrm{\#3SAT}\in\mathrm{NP}$. I said don't do that; reduce an $\mathrm{NP}$-complete problem to it. Then you tried to produce an algorithm for $\mathrm{\#3SAT}$ and I said don't do that; reduce an $\mathrm{NP}$-complete problem to it. It doesn't seem to me that you've spent any time trying to actually reduce an $\mathrm{NP}$-complete problem to $\mathrm{\#3SAT}$. It's only eight minutes since I last told you to do that and you showed no evidence of having tried to do it before then. – David Richerby Jun 17 at 10:17
• One last question, I noticed that you have edited your answer by adding a comment on the length of the certificate. I understand what you wrote but it seems to me that it is correct only if you take into consideration the space of all possible certificates. Basically what I was saying was this: if you have an instance of # 3SAT with y = 10, The certificate that must be given as a meal to the verifier must contain only 10 different distributions of variables that make the input belonging to # 3SAT(10) and therefore it will be only 10 times larger than the 3SAT's one. – Yamar69 Jun 17 at 10:36

The subset for $$y = 1$$ is 3SAT, which is NP-complete (thus NP-hard); the full set can't be easier...