Examples of #P-complete problems include:
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.