* Are there any solutions that satisfy this these constraints? |
* Are there any solutions that satisfy certain constraints? |
* Are there any subsets of a list of integers that add up to zero? * Are there any tours in a [Traveling Salesman Problem]? of length less than 100? * Are there any variable assignments that satisfy this DNF formula? |
* Are there any subsets of a list of integers that add up to zero? ([subset sum problem]?) * Are there any [Hamiltonian cycle]?s in a given graph with cost less than 100? (traveling salesman problem) * Are there any variable assignments that satisfy a given DNF? formula? ([satisfiability problem]?) |
* How many tours in a [Traveling Salesman Problem]? have length less than 100? * How many variable assignments satisfy this DNF formula? |
* How many Hamiltonian cycles in a given graph have cost less than 100? * How many variable assignments satisfy a given DNF formula? |
More formally, a problem is in #P if there is a nondeterministic, polynomial-time Turing machine that, for each instance I of the problem, has a number of accepting computations that is exactly equal to the number of distinct solutions to instance I. |
More formally, a problem is in #P if there is a nondeterministic, polynomial-time Turing machine that, for each instance I of the problem, has a number of accepting computations that is exactly equal to the number of distinct solutions for instance I. |
An NP problem is often of the form:
More formally, a problem is in #P if there is a nondeterministic, polynomial-time Turing machine that, for each instance I of the problem, has a number of accepting computations that is exactly equal to the number of distinct solutions for instance I.
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.