An **NP** problem is often of the form:

- Are there any solutions that satisfy certain constraints?

- Are there any subsets of a list of integers that add up to zero? (subset sum problem)
- Are there any Hamiltonian cycles in a given graph with cost less than 100? (traveling salesman problem)
- Are there any variable assignments that satisfy a given DNF formula? (Boolean satisfiability problem)

- How many subsets of a list of integers add up to zero?
- How many Hamiltonian cycles in a given graph have cost less than 100?
- How many variable assignments satisfy a given DNF formula?

Clearly, a **#P** problem must be at least as hard as the corresponding **NP** problem. If it's easy to count answers, then it must be easy to tell whether there are any answers. Just count them, and see if the count is greater than zero. Therefore, the **#P** problem corresponding to any **NP-Complete** problem, must be **NP-Hard**.

Surprisingly, some **#P** problems that are believed to be difficult correspond to easy **P** problems. For more information on this, see **Sharp-P-Complete**.