Permanents is a package of functions for computing the permanent of a square matrix.
Computing the permanent is believed to be computationally intractible. In Valiant’s theory of algebraic complexity the permanent polynomial is complete for the class VNP. Even computing the permanent of 0-1 matrices is #P-complete. See Valiant, Leslie G. (1979), "The Complexity of Computing the Permanent," Theoretical Computer Science (Elsevier) 8 (2): 189-201.
The permanent of a n×n matrix (xi,j) is defined in analogy to the determinant as ∑σ∈Sn ∏xi,σ(i). There are two other formulas for the permanent polynomial, Ryser’s formula and Glynn’s formula, both of which have the assymptotically smaller formula size of O(2n n2). This can be improved further to O(2n n) arithmetic operations with the use of Gray codes, and we do so in this package. The connection between the two formulae and the possibility of others is discussed in Glynn, David G. (2013), "Permanent Formulae from the Veronesean." Designs Codes and Cryptography, 68(1-3) pp. 39-47.
It is conjectured that the permanent polynomial does not have a polynomial size formula. By Valiant’s theory, a possible strategy for proving this is to show that the permanent of the n×n generic matrix N cannot be the determinant of a p(n) ×p(n) matrix M with entries affine linear entries of the variables of M where p(n) is a polynomial. The best lower bound is quadartic, i.e. the permanent of the nxn generic matrix is not the affine projection of the determinant of a n2/2xn2/2 matrix. See T. Mignon, N. Ressayre. "A Quadratic Bound for the Determinant and Permanent Problem." (2004).