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.