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?
- What is the permanent of a given matrix?
- How many perfect matchings are there for a given bipartite graph?
However, there are probabilistic algorithms 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.
It is surprising that some #P-complete problems correspond to easy P problems. The third example problem above is in this category. The question "Is there a perfect matching for a given bipartite graph?" can be answered in polynomial time. In fact, for a graph with V vertices and E edges, it can be answered in O(VE) time. The corresponding question "how many perfect matchings does the given bipartite graph have?" is #P-complete.