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:
“History is the interpretation of the significance that the past has for us.”
—Johan Huizinga (1872–1945)
“Politics is not an end, but a means. It is not a product, but a process. It is the art of government. Like other values it has its counterfeits. So much emphasis has been placed upon the false that the significance of the true has been obscured and politics has come to convey the meaning of crafty and cunning selfishness, instead of candid and sincere service.”
—Calvin Coolidge (1872–1933)
“For a parent, it’s hard to recognize the significance of your work when you’re immersed in the mundane details. Few of us, as we run the bath water or spread the peanut butter on the bread, proclaim proudly, “I’m making my contribution to the future of the planet.” But with the exception of global hunger, few jobs in the world of paychecks and promotions compare in significance to the job of parent.”
—Joyce Maynard (20th century)