The permanent of a matrix has a simple form

_{σ }a

_{1&sigma(1)}a

_{2&sigma(2)}···a

_{n&sigma(n)}

where A is an n×n matrix, a_{ij} is the element in the
ith row and jth column and the sum is taken over all permutations σ of
{1,…,n}.

Very similar to the determinant except without the negations and a 0-1 permanent counts the number of perfect matchings on a bipartite graph. But while we can compute the determinant quickly and easily check if a graph has a perfect matching the permanent turns out to have an apparently much higher complexity.

Valiant shows that computing the permanent, even for 0-1 matrices, is #P-complete, i.e., as hard as counting the number of solutions for NP problems.

While an important hardness result in its own right, Valiant's theorem becomes even more important with later work. Toda's theorem implies the permanent is hard for the entire polynomial-time hierarchy. The permanent also has two very important properties:

- The permanent on n×n matrices is easily reducible to solving the permanent on (n-1)×(n-1) matrices.
- The permanent is a multilinear polynomial on the entries of A.

Other nice results that are worth mentioning are "Clifford algebras and approximating the permanent" and "A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries"

ReplyDelete"Other nice results that are worth mentioning..."

ReplyDeleteThe paper on Clifford algebras has a "result"? Who knew?

Another nice result on the permanent,

ReplyDeletealso due to Valiant, is its completeness

for the class VNP of "easily definable"

families of polynomials.

This implies that the permanent can be

evaluated in a polynomial number of arithmetic operations iff all

"easily definable" families of polynomials

can.

Another interesting result on the permanent:

ReplyDeleteComputing Permanents over Fields of Characteristic 3: Where and Why It Becomes Difficult (extended abstract). FOCS 1996