Previous CCW Let A={a

_{ij}} be an n×n matrix over the integers. The determinant of the A is defined asDet(A)=Σ 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._{σ}(-1)^{|σ|}a_{1σ(1)}a_{2σ(2)}...a_{nσ(n)}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)=Σ Suppose G is a bipartite graph and let a_{σ}a_{1σ(1)}a_{2σ(2)}...a_{nσ(n)}_{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.

--

Posted by Lance Fortnow to My Computational Complexity Web Log at 3/13/2003 2:49:21 PM

Powered by Blogger Pro