Computing the permanent

In <a href="/facts/Linear_algebra/8VaB4VWk">linear algebra</a>, the computation of the <a href="/facts/Permanent_(mathematics)/eJWgdahx">permanent</a> of a <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a> is a problem that is thought to be more difficult than the computation of the <a href="/facts/Determinant/eGYqJ2TF">determinant</a> 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 <a href="/facts/Parity_of_a_permutation/ludhCMJz">parity of the set</a>, the permanent weights them all with a +1 sign.
While the determinant can be computed in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> by <a href="/facts/Gaussian_elimination/23Rvf4ht">Gaussian elimination</a>, it is generally believed that the permanent cannot be computed in polynomial time. In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, <a href="/facts/Permanent_is_sharp-P-complete/GdIk6oqw">a theorem of Valiant</a> states that computing permanents is <a href="/facts/Sharp-P-complete/M6QgPJY6">#P-hard</a>, and even <a href="/facts/Sharp-P-complete/M6QgPJY6">#P-complete</a> for matrices in which all entries are 0 or 1 Valiant (1979). This puts the computation of the permanent in a class of problems believed to be even more difficult to compute than <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>. It is known that computing the permanent is impossible for logspace-uniform <a href="/facts/ACC0/cetNt48W">ACC0</a> 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.

Computing the permanent open-in-new

Computing the permanent