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:
| “ | The most impressive and interesting #P-complete problems are those for which the corresponding search problem can be solved in polynomial time. The PERMANENT problem for 0–1 matrices, which is equivalent to the problem of counting perfect matchings in a bipartite graph is the classic example here. | ” |
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.
Read more about this topic: Permanent Is Sharp-P-complete
Famous quotes containing the word significance:
“The hysterical find too much significance in things. The depressed find too little.”
—Mason Cooley (b. 1927)
“The hypothesis I wish to advance is that ... the language of morality is in ... grave disorder.... What we possess, if this is true, are the fragments of a conceptual scheme, parts of which now lack those contexts from which their significance derived. We possess indeed simulacra of morality, we continue to use many of the key expressions. But we have—very largely if not entirely—lost our comprehension, both theoretical and practical, of morality.”
—Alasdair Chalmers MacIntyre (b. 1929)
“History is the interpretation of the significance that the past has for us.”
—Johan Huizinga (1872–1945)