Sharp-P-Complete

#P-Complete, pronounced "sharp P complete", is a complexity class in complexity theory. A problem is in #P-Complete if and only if it is in #P, and every problem in #P can be reduced to it in polynomial time.

Examples of #P-Complete problems include:

• How many different variables assignments will satisfy a given DNF? formula?
• How many [perfect matching]?s are there for a given graph?
• What is the permanent? of a given matrix?

It is believed that there is no polynomial-time algorithm for solving #P-Complete problems. If it is difficult to solve exactly, then can it even be approximated? No deterministic algorithm is known that can even find the approximate answer to within some reasonable error bound.

However, there are [probabilistic algorithm]?s that return good approximatations to some #P-Complete problems with high probability. This is one of the most striking demonstrations of the power of probabilistic algorithms.