Main Page | See live article | Alphabetical index

Sharp-P

#P, pronounced "sharp P", is a complexity class in complexity theory. It is the set of counting problems associated with the decision problems in the set NP.

An NP problem is often of the form:

For example: The corresponding #P problems ask "how many" rather than "are there any". For example: More formally, a problem is in #P if there is a non-deterministic, 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.