Home › Multilingual Archive Index › Sharp-P-complete

Sharp-P-complete

#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 by a polynomial-time counting reduction, i.e. a polynomial-time Turing reduction relating the cardinalities of solution sets. Very often the reductions are "parsimonious," i.e., they preserve the number of solutions.

Examples of #P-complete problems include:

• How many different variable assignments will satisfy a given DNF formula?
• How many different variable assignments will satisfy a given 2SAT formula?
• What is the value of the permanent of a given matrix?
• How many perfect matchings are there for a given bipartite graph?
• How many graph colorings using k colors are there for a particular graph G?

A polynomial-time algorithm for solving a #P-complete problem, if it existed, would imply P = PH, and thus P = NP. No such algorithm is currently known.

Relationship to other complexity classes

It is surprising that some #P-complete problems correspond to easy P problems. The first, second, and fourth problems from the examples above fall 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. 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. The permanent was the first counting problem corresponding to an easy P problem shown to be #P-complete, in a 1979 paper by Leslie Valiant which also defined the classes #P and #P-complete for the first time.^[1]

Similarly, there is a trivial algorithm for determining if a DNF form is satisfiable: examine each clause, and if a satisfiable clause is found (one that does not contain a variable and its negation) then it is satisfiable, otherwise it is not. The counting version of this problem is #P-complete.

Approximation

If it is difficult to evaluate a counting function exactly, then can it at least be approximated? The answer turns out to be yes, in many cases. 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.

Many #P-complete problems have a fully-polynomial-time randomized approximation scheme, or "FPRAS," which, informally, will produce with high probability an approximation to an arbitrary degree of accuracy, in time that is polynomial with respect to both the size of the problem and the degree of accuracy required. Jerrum, Valiant, and Vazirani showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if there is any polynomial-time algorithm which consistently produces an approximation of a #P-complete problem which is within a polynomial ratio in the size of the input of the exact answer, then that algorithm can be used to construct an FPRAS.^[2]

References

1. ^ Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science 8: 189-201. Elsevier. 
2. ^ Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). "Random Generation of Combinatorial Structures from a Uniform Distribution". Theoretical Computer Science 32: 169-188. Elsevier. 

Further reading

• Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3540653678.