I need some hints to solve the following problem. (from Complexity and cryptography by Talbot and Welsh, chapter 3, exercise 3.6)
Let #SAT be the function, mapping Boolean formulae in CNF to $\mathbb Z^+$ defined
$\text{#SAT}(f) = |\{a \in \{0, 1\}^n | f (a) = 1\}|$
Show that #SAT is NP-hard.
Though it talks about a different NP-hard problem, this might be of help. Essentially, you need to show that (1) given a proposed satisfying solution $a$, you can verify its correctness in time polynomial in its length using a deterministic Turing Machine or, equivalently, that (2) you can find a satisfying solution in poly time using a nondeterministic TM.