Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Complexity Class of the Week: The Permanent

Expand Messages
  • Lance Fortnow
    Previous CCW Let A={a ij } be an nn 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
    Message 1 of 1 , Mar 13, 2003
    • 0 Attachment
      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.

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

      Powered by Blogger Pro

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