Thursday, March 13, 2003

Complexity Class of the Week: The Permanent

Previous CCW

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

Det(A)=Σσ(-1)|σ| a1σ(1)a2σ(2)...anσ(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)=Σσ a1σ(1)a2σ(2)...anσ(n)
Suppose G is a bipartite graph and let aij 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.

No comments:

Post a Comment