# What are some applications of computing the permanent of a matrix?

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.

• There is the question of permanent VS determinant. I think that one can easily compute the determinant using the permanent on a bigger matrix, but the main question is how to compute the permanent using the determinant. – Tpecatte Sep 19 '13 at 11:21

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.
• No, but SAT solvers are used universally exactly because SAT is NP-complete. The importance of the permanent in TCS lies in its $\# P$ universality. – Yuval Filmus Sep 20 '13 at 2:03