♯P

In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete.

==Relation to decision problems== An NP decision problem can often be stated in the form "Are there any solutions that satisfy certain constraints?" For example: 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 CNF (conjunctive normal form) formula? (Boolean satisfiability problem or SAT) Does a univariate real polynomial have any positive roots? (root finding)