Permanent Is Sharp-P-complete - Significance

Significance

One reason for interest in the computational complexity of the permanent is that it provides an example of a problem where constructing a single solution can be done efficiently but where counting all solutions is hard. As Papadimitriou writes in his book Computational Complexity:

Specifically, computing the permanent (shown to be difficult by Valiant's results) is closely connected with finding a perfect matching in a bipartite graph, which is solvable in polynomial time by the Hopcroft–Karp algorithm. For a bipartite graph with 2n vertices partitioned into two parts with n vertices each, the number of perfect matchings equals the permanent of its biadjacency matrix and the square of the number of perfect matchings is equal to the permanent of its adjacency matrix. Since any 0–1 matrix is the biadjacency matrix of some bipartite graph, Valiant's theorem implies that the problem of counting the number of perfect matchings in a bipartite graph is #P-complete, and in conjunction with Toda's theorem this implies that it is hard for the entire polynomial hierarchy.

The computational complexity of the permanent also has some significance in other aspects of complexity theory: it is not known whether NC equals P (informally, whether every polynomially-solvable problem can be solved by a polylogarithmic-time parallel algorithm) and Ketan Mulmuley has suggested an approach to resolving this question that relies on writing the permanent as the determinant of a matrix.

Hartmann proved a generalization of Valiant's theorem concerning the complexity of computing immanants of matrices that generalize both the determinant and the permanent.