Computational Complexity

Thursday, March 13, 2003

 
Complexity Class of the Week: The Permanent

Posted by Lance

Previous CCW

Let A={a_ij} be an n×n matrix over the integers. The determinant of the A is defined as

Det(A)=Σ_σ(-1)^|σ| a_1σ(1)a_2σ(2)...a_nσ(n) where σ ranges over all permutations on n elements and |σ| is the number of 2-cycles one has to apply to σ to get back the identity.

The determinant is computable efficiently using Gaussian Elimination and taking the product of the diagonal.

The permanent has a similar definition without the -1 term. We define the permanent of A by

Perm(A)=Σ_σ a_1σ(1)a_2σ(2)...a_nσ(n) Suppose G is a bipartite graph and let a_ij be 1 if there is an edge from the ith node on the left to the jth node on the right and 0 otherwise. Then Perm(A) is the number of perfect matchings in G.

Unlike the determinant the permanent seems quite hard to compute. In 1979, Valiant showed that the permanent is #P-complete, i.e., computing the permanent is as hard as counting the number of satisfying assignments of a Boolean formula. The hardness of the permanent became more clear after Toda's Theorem showing that every language in the polynomial-time hierarchy is reducible to a #P problem and then the permanent.

The permanent is difficult to compute even if all the entries are 0 and 1. However determining whether the permanent is even or odd is easy since Perm(A) = Det(A) mod 2.

Since we can't likely compute the permanent exactly, can we approximate it? The big breakthrough came a few years ago in a paper by Jerrum, Sinclair and Vigoda showing how to approximate the permanent if the entries are not negative.

1:49 PM # 0 comments

Comment Feeds: This Post All