Wikipedia
#P-complete, pronounced "sharp P complete" or "number P complete" is a complexity class in computational complexity theory. By definition, a problem is #P-complete if and only if it is in #P, and every problem in #P can be reduced to it by a polynomial-time counting reduction, i.e. a polynomial-time Turing reduction relating the cardinalities of solution sets. Equivalently, a problem is #P-complete if and only if it is in #P, and for any non-deterministic Turing machine, the problem of computing its number of accepting paths can be reduced to this problem.
Examples of #P-complete problems include:
- How many different variable assignments will satisfy a given general boolean formula? ( #SAT)
- How many different variable assignments will satisfy a given DNF formula?
- How many different variable assignments will satisfy a given 2SAT formula?
- How many perfect matchings are there for a given bipartite graph?
- What is the value of the permanent of a given matrix whose entries are 0 or 1? (See Permanent is sharp-P-complete.)
- How many graph colorings using k colors are there for a particular graph G?
- How many different linear extensions are there for a given partial order, or, equivalently, how many different topological orderings are there for a given directed acyclic graph?
A polynomial-time algorithm for solving a #P-complete problem, if it existed, would imply P = NP, and thus P = PH. No such algorithm is currently known.