Sharp-P-complete
From Wikipedia, the free encyclopedia
- The correct title of this article is #P-complete. The substitution or omission of a # sign is because of technical restrictions.
#P-complete, pronounced "sharp P complete", is a complexity class in complexity theory. A problem is #P-complete if and only if it is in #P, and every problem in #P can be reduced to it in logarithmic space (we actually require a stronger form of reduction, a "parsimonious reduction" that also preserve the number of solutions between mapped problems).
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?
It is believed that there is no polynomial-time algorithm for solving #P-complete problems, since this would imply P = PH, and thus P = NP. 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 approximations 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 problem from the examples above falls in this category: It was known before that the decision problem "Is there a perfect matching for a given bipartite graph?" can be solved in polynomial time, and in fact, for a graph with V vertices and E edges, it can be solved in O(VE) time. Astonishingly, the corresponding question "How many perfect matchings does the given bipartite graph have?" is already #P-complete. The problem of counting the number of perfect matchings (or in directed graphs: the number of cycle covers) is known as the Permanent.
| Important complexity classes (more) |
|---|
| P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • EXPSPACE • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH |
