Redirected from SharpPComplete
Examples of #Pcomplete problems include:
It is believed that there is no polynomialtime algorithm for solving #Pcomplete 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 algorithms that return good approximatations to some #Pcomplete problems with high probability. This is one of the most striking demonstrations of the power of probabilistic algorithms.
It is surprising that some #Pcomplete 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 #Pcomplete.
Search Encyclopedia
