Given ** #3SAT** =

$ \{\ w, y\ |\ w \ is \ a \ 3SAT \ instance \ which \ has \ at \ least \ y \ satisfying \ assignments \}\ $

Prove that ** #3SAT** is NP-Hard.

I am currently stuck with this one.

Basically ** #3SAT** is the counting version of 3SAT and to me it is seems clear that establishing membership in the language is more complex than establish the classic 3-SAT membership.

I’m trying to reason through the prover-verifier paradigm: lets say you have a 3-SAT instance, now suppose the certificate for that instance is $ n \ bit$ . It is obvious that the certificate for the same instance but translated into

**with lets say $ y=10$ would be at least $ 10n \ bit$ . So if the first can be examined in $ Polynomial \ time(t)$ then the second will take at least $ 10∗(t)$ and so on. However I am not satisfied with this reasoning, it seems incomplete and superficial. I would greatly appreciate your advices on how to proceed with this proof. Thanks in advance.**

*#3SAT*