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.

  • $\begingroup$ 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. $\endgroup$
    – 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.

  • 2
    $\begingroup$ While that's true, I don't think it's an application of computing the permanent per se. I don't think you'd say, for example, that an application of the travelling salesman problem is determining whether a 3-CNF formula is satisfiable. $\endgroup$ Sep 19 '13 at 19:51
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 20 '13 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.