Computing the permanent
 | This article or section is in a state of significant expansion or restructuring. You are welcome to assist in its construction by editing it as well. If this article or section has not been edited in several days, please remove this template. If you are the editor who added this template and you are actively editing, please be sure to replace this template with {{in use}} during the active editing session. Click on the link for template parameters to use.
This article was last edited by Twri (talk | contribs) 16 years ago. (Update timer) |
In mathematics, the computation of the permanent of a matrix is a problem more complex than the computation of the determinant of a matrix despite the apparent similarity of the definitions.
While the determinant can be computed in polynomial time by Gaussian elimination, Gaussian elimination cannot be used to compute the permanent.
It turns out that computing the permanent of a 0-1-matrix (a matrix whose entries are 0 or 1) is already #P-complete (proof).[1][2] Thus, if the permanent can be computed in polynomial time by any method, then FP = #P which is an even stronger statement than P = NP.
When the entries of A are nonnegative, the permanent can be computed approximately in probabilistic polynomial time, up to an error of εM, where M is the value of the permanent and ε > 0 is arbitrary. Because the permanent is random self-reducible, these results hold out even for average-case inputs. [3]
References
- ^ Ben-Dor, Amir and Halevi, Shai. (1993). "Zero-one permanent is #P-complete, a simpler proof". Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, 108-117.
- ^ Valiant, L.G. (1979). "The complexity of computing the permanent". Theoretical Computer Science 8, 189-201.
- ^ Jerrum, Sinclair, and Vigoda. (2001). "A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries". Theory of Computing, 712-721.