*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 *(x _{i,j})* is defined in analogy to the determinant as

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 *n ^{2}/2xn^{2}/2* matrix. See T. Mignon, N. Ressayre. "A Quadratic Bound for the Determinant and Permanent Problem." (2004).

The best known upper bound is *2 ^{n}-1* due to Grenet. More specifically, Grenet constructs a

Computationally intensive

- permanents -- ideal generated by square permanents of a matrix
- determinant -- determinant of a matrix

This documentation describes version **0.9** of Permanents.

The source code from which this documentation is derived is in the file Permanents.m2.