patternMinor
What are some applications of computing the permanent of a matrix?
Viewed 0 times
thewhatareapplicationssomepermanentmatrixcomputing
Problem
What are some applications that require computing the permanent of a matrix?
One application I know of is related to graph theory and matchings. Apparently, the number of perfect matchings of a bipartite graph is the permanent of its incidence matrix.
I am curious to know more applications of matrix permanent.
One application I know of is related to graph theory and matchings. Apparently, the number of perfect matchings of a bipartite graph is the permanent of its incidence matrix.
I am curious to know more applications of matrix permanent.
Solution
Valiant proved that the permanent is $\# P$-complete, which means that an efficient algorithm for computing the permanent can be used to solve any problem in $\# P$, such as counting the number of satisfying assignment to a CNF, the number of Hamiltonian circuits, the number of $k$-colorings and so on. In particular, it could be used to solve NP-complete problems.
Context
StackExchange Computer Science Q#14438, answer score: 5
Revisions (0)
No revisions yet.