4
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2013 at 11:21

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • 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, 2013 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, 2013 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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