3

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.

Gigili
  • 5,503
  • 8
  • 41
  • 62
  • Could you add the definition of NP you're using and whether you've proven anything else is NP-hard? – Kevin Carlson Jul 09 '13 at 06:50
  • 5
    Hint: Formula is satisfiable if and only if has at least one satisfying assignment. – Peter Košinár Jul 09 '13 at 06:55
  • @PeterKošinár: Thanks, but I see no relevance between your hint which is a basic concept and the problem I am trying to solve. Plus that, not iff there's at least one satisfying assignment, but iff there's at least one satisfying truth assignment. – Gigili Jul 10 '13 at 05:23
  • Let's expand the hint a bit: In order to show that #SAT is NP-hard, it suffices to show that it is at least as difficult as another, already-known-to-be-NP-hard problem. In this case, SAT (known to be NP-complete) is a natural choice for this "other" problem. My hint pointed out the (yes, trivial) connection between SAT which asks "is the formula satisfiable" and #SAT which asks "how many satisfying assignments does the formula have". – Peter Košinár Jul 10 '13 at 07:23
  • @PeterKošinár: Got it, thank your for your further explanation. – Gigili Jul 10 '13 at 19:28

1 Answers1

0

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.

Community
  • 1
Rick Decker
  • 8,718