HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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.

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.