## [Computational Complexity] Favorite Theorems: The Permanent

Expand Messages
• June Edition The permanent of a matrix has a simple form Perm(A)= a 1&sigma(1) a 2&sigma(2) a n&sigma(n) where A is an nn matrix, a ij is the element in the
Message 1 of 2 , Jul 24, 2006
June Edition

The permanent of a matrix has a simple form

Perm(A)=Σσa1&sigma(1)a2&sigma(2)···an&sigma(n)

where A is an n×n matrix, aij 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.

Leslie Valiant, The Complexity of Computing the Permanent, TCS 1979.

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:

1. The permanent on n×n matrices is easily reducible to solving the permanent on (n-1)×(n-1) matrices.
2. The permanent is a multilinear polynomial on the entries of A.
Those two facts, combined with Valiant's and Toda's theorems, helped the permanent play a critical role in the development of interactive proofs and in some derandomization results, most notably Impagliazzo-Wigderson and Impagliazzo-Kabanets.

--
Posted by Lance to Computational Complexity at 7/24/2006 08:15:00 AM

• June Edition The permanent of a matrix has a simple form Perm(A)= a 1&sigma(1) a 2&sigma(2) a n&sigma(n) where A is an nn matrix, a ij is the element in the
Message 2 of 2 , Jul 24, 2006
June Edition

The permanent of a matrix has a simple form

Perm(A)=Σσa1&sigma(1)a2&sigma(2)···an&sigma(n)

where A is an n×n matrix, aij 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.

Leslie Valiant, The Complexity of Computing the Permanent, TCS 1979.

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:

1. The permanent on n×n matrices is easily reducible to solving the permanent on (n-1)×(n-1) matrices.
2. The permanent is a multilinear polynomial on the entries of A.
Those two facts, combined with Valiant's and Toda's theorems, helped the permanent play a critical role in the development of interactive proofs and in some derandomization results, most notably Impagliazzo-Wigderson and Impagliazzo-Kabanets.

--
Posted by Lance to Computational Complexity at 7/24/2006 08:15:00 AM

Your message has been successfully submitted and would be delivered to recipients shortly.