Computing The Permanent
In mathematics, the computation of the permanent of a matrix is a problem that is known to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of the definitions.
The permanent is defined similarly to the determinant, as a sum of products of sets of matrix entries that lie in distinct rows and columns. However, where the determinant weights each of these products with a ±1 sign based on the parity of the set, the permanent weights them all with a +1 sign.
While the determinant can be computed in polynomial time by Gaussian elimination, the permanent cannot. In computational complexity theory, a theorem of Valiant states that computing permanents, even of matrices in which all entries are 0 or 1, is #P-complete Valiant (1979) putting the computation of the permanent in a class of problems believed to be even more difficult to compute than NP. It is known that computing the permanent is impossible for logspace-uniform ACC0 circuits (Allender & Gore 1994).
The development of both exact and approximate algorithms for computing the permanent of a matrix is an active area of research.
Read more about Computing The Permanent: Definition and Naive Algorithm, Ryser Formula, Glynn Formula, Approximate Computation
Famous quotes containing the word permanent:
“Self-expression is not enough; experiment is not enough; the recording of special moments or cases is not enough. All of the arts have broken faith or lost connection with their origin and function. They have ceased to be concerned with the legitimate and permanent material of art.”
—Jane Heap (c. 1880–1964)