Permanent is sharp-P-complete

From Wikipedia, the free encyclopedia

The correct title of this article is Permanent is #P-complete. The substitution or omission of a # sign is because of technical restrictions.

This page gives a mathematical proof that computing the permanent of a 01-matrix is #P-complete. The proof given here follows Ben-Dor and Halevi (1993). The first proof of this fact was given by Leslie Valiant (1979).

The 01-Permanent problem arises in a surprising place: The number of perfect matchings in a bipartite graph is equal to the permanent of its adjacency matrix. There is a polynomial time algorithm for determining if a perfect matching exists, but this result shows that it is significantly harder to count the number of those matchings.

It is also worth noting that a polynomial time approximation algorithm exists for computing the permanent. Jerrum, Sinclair, and Vigoda (2001) gave an algorithm that will produce an answer arbitrarily close to the exact value of the permanent for a 01-matrix.

1 Proof overview
2 Permanent of Graphs
- 2.1 Permanent Counts Cycle-Covers
- 2.2 Permanent Counts Perfect Matchings
3 Constructing the Integer Graph
- 3.1 A Very Nice Property of the Graph
- 3.2 The Clause Component
4 01-Matrix
5 References

[edit] Proof overview

In order to prove that Permanent is #P-hard, it is sufficient to show that #SAT, a #P-complete problem, can be expressed as the permanent of some 01-matrix. The #SAT function problem, related to the boolean satisfiability problem, asks the question: "How many satisfying assignments exist for a given boolean formula?" Any formula in SAT could be rewritten as a formula in 3-CNF form preserving the number of satisfying assignments and so the equivalence between #SAT and #3-SAT is established. The proof in this article shows how the number of satisfying assignments for a 3-CNF formula φ can be expressed succinctly as a function of the permanent of a matrix that contains only the values 0 and 1. This is accomplished in several steps:

Given a 3-CNF formula φ, construct a directed integer-weighted graph $G φ$ .
Show that the sum of the weights of all cycle covers of $G φ$ is equal to the permanent of the graph's adjacency matrix.
Reduce this graph to one having only positive weights on its edges.
Reduce the new graph to one having weights of only 0 or powers of 2.
Apply another reduction to produce a graph that only has weights of 0 or 1. Then the number of satisfying assignments of φ is exactly equal to the number of cycle covers of this reduced graph which is in turn given by the permanent of the graph's adjacency matrix.

Thus, there is a reduction from the problem of calculating the number of satisfying assignments for φ to computing the permanent of a matrix with only 0s and 1s.

As a forewarning, the graph construction makes use of a component that is treated as a "black box." To keep the explanation simple, the properties of this component are given without actually defining the structure of the component.

[edit] Permanent of Graphs

Any matrix can be viewed as the adjacency matrix of a graph (a non-square matrix could be mapped onto a square matrix by padding rows or columns of zeros) with each entry in the matrix representing the weight of an edge connecting the vertices determined by the row and column of the entry. So there is a direct correspondence between a graph and a matrix.

[edit] Permanent Counts Cycle-Covers

A cycle-cover of a weighted directed graph is a collection of node-disjoint directed cycles in the graph that covers all nodes (say there are n of them) in the graph. A permutation on ${1,2,..., n}$ is just a function that maps elements into disjoint cycles, so a permutation is a natural representation of a cycle-cover. The weight of a cycle-cover is defined to be the product of the weights of the edges in each cycle:

$Weight(\sigma) = \Pi_{i=1}^n a_{i,\sigma(i)}$

where $σ$ is a cycle-cover represented as a permutation and $a i, j$ is the weight of the edge from i to j.

The permanent of an $n \times n$ matrix A is defined as follows:

$Perm(A)=\Sigma_\sigma \Pi_{i=1}^{n} a_{i,\sigma(i)}$

where $σ$ is a permutation over ${1,2,..., n}$ . Intuitively, the permanent is the sum of product terms where each product term consists of $n$ matrix entries such that there is at least one matrix entry from every row and every column in the matrix.

Now, take any n-node graph G and its $n \times n$ adjacency matrix A. From the definitions of a permanent and a cycle-cover given above, we see that the permanent of A is equivalent to the sum of the weights of all cycle-covers of G. The permanent sums over a term ( $Π...$ ) for every permutation $σ$ on ${1,2,..., n}$ , some of which might be cycle-covers. If $σ$ is a cycle-cover of G, the term is just the weight of that cycle-cover. If $σ$ is not a cycle-cover of G, there is some factor in the term, say $a i,σ(i)$ , where there is no edge from i to $σ(i)$ in the graph. Then in the adjacency matrix, $a i,σ(i) = 0$ so the whole term $Π... a i,σ(i) ... = 0$ . The only terms that contribute to the sum are the weights of every cycle-cover of G.

Calculating the permanent of a 01-matrix is equivalent to computing the number of cycle-covers of an unweighted directed graph. This problem is called 01-Perm.

[edit] Permanent Counts Perfect Matchings

In bipartite and undirected graphs, we replace every undirected edge by two directed edges. Then every cycle-cover in the directed version corresponds to a perfect matching of the undirected one (since every ). Therefore the permanent of the adjacency matrix of a bipartite and undirected graph counts the number of perfect matchings.

[edit] Constructing the Integer Graph

Given a 3CNF-formula $φ$ , let m be the number of clauses in $φ$ and n be the number of variables in $φ$ . Construct a weighted, directed graph $G φ$ such that (1) each satisfying assignment for $φ$ will have a corresponding set of cycle covers in $G φ$ where the sum of the weights of cycle covers in this set will be $12 m$ and (2) all other cycle covers in $G φ$ will have weights summing to 0. Where $S (φ)$ is the number of satisfying assignments for $φ$ , then, this graph will be such that the permanent of its adjacency matrix (which we can also denote as $G φ$ since there is a one-to-one mapping of such graphs to adjacency matrices) is $12 m * S (φ)$ . Thus, by solving Perm( $G φ$ ), we will be able to determine the number of satisfying assignments of $φ$ , $S (φ)$ .

To specify $G φ$ , we first construct a variable node in $G φ$ for each of the n variables in $φ$ . Additionally, for each of the m clauses in $φ$ , we construct is a clause component $C j$ in $G φ$ that functions as a sort of "black box." For present purposes, all that needs to be noted about $C j$ is that it has three input edges and three output edges. The input edges come either from variable nodes or from previous clause components (e.g., $C o$ for some $o < j$ ) and the output edges go either to variable nodes or to later clause components (e.g., $C o$ for some $o > j$ ). The first input and output edges correspond with the first variable of the clause j, and so on. Thus far, all of the nodes that will appear in the graph $G φ$ have been specified.

Now for the edges. For each variable $x i$ of $φ$ , make a true cycle (T-cycle) and a false cycle (F-cycle) in $G φ$ . To create the T-cycle, we start at the variable node for $x i$ and draw an edge to the clause component $C j$ that corresponds to the first clause in which $x i$ appears. If $x i$ is the first variable in the clause of $φ$ corresponding to $C j$ , this edge will be the first input edge of $C j$ , and so on. Thence, draw an edge to the next clause component corresponding to the next clause of $φ$ in which $x i$ appears, connecting it from the appropriate output edge of $C j$ to the appropriate input edge of the next clause component, and so on. After the last clause in which $x i$ appears, we connect the appropriate output edge of the corresponding clause component back to $x i$ 's variable node. Of course, this completes the cycle. To create the F-cycle, we follow the same procedure but connect $x i$ 's variable node to those clause components in which ~ $x i$ appears and finally back to $x i$ 's variable node. All of these edges outside the clause components we term external edges, all of which have weight 1. Inside the clause components, we term the edges internal edges. Now, clearly, every external edge is part of a T-cycle or an F-cycle (but not both--that would force inconsistency).

Note that the graph $G φ$ is of size linear in $| φ |$ , so the construction can be done in polytime (assuming that the clause components don't cause trouble, which they don't).

[edit] A Very Nice Property of the Graph

Now, $G φ$ has the very nice property that its cycle covers correspond to variable assignments for $φ$ . Anyway, for a cycle cover Z of $G φ$ , we can say that Z induces an assignment of values for the variables in $φ$ just in case Z contains all of the external edges in $x i$ 's T-cycle and none of the external edges in $x i$ 's F-cycle for all variables $x i$ that the assignment makes true, and vice versa for all variables $x i$ that the assignment makes false. Although any given cycle cover Z need not induce an assignment for $φ$ , any one that does induces exactly one assignment, and the same assignment induced depends only on the external edges of Z. We consider Z an incomplete cycle cover at this stage because we talk only about its external edges, M. In the section below, we consider M-completions to show that we have a set of cycle covers corresponding to each M that have the necessary properties.

Now, the sort of Z's that don't induce assignments are the ones with cycles that "jump" inside the clause components. That is, if for every $C j$ , at least one of $C j$ 's input edges is in Z, and every output edge of the clause components is in Z when the corresponding input edge is in Z, then we can say that Z is proper with respect to each clause component, and we can be assured the Z will produce a satisfying assignment for $φ$ . This is because proper Z's contain either the complete T-cycle or the complete F-cycle of every variable $x i$ in $φ$ as well as each including edges going into and coming out of each clause component. Thus, these Z's assign either true or false (but, of course, never both) to each $x i$ and ensure that each clause is satisfied. Further, the sets of cycle covers corresponding to all such Z's have weight $12 m$ , and any other Z's have weight $0$ . The reasons for this depend on the construction of the clause components, and are outlined below.

[edit] The Clause Component

To understand the relevant properties of the clause components $C j$ , we need one more notion: that of an M-completion. Recall that in the previous section, a cycle cover Z induced a satisfying assignment just in case its external edges satisfied certain properties. Now for any cycle cover of $G φ$ , we'll consider only its external edges, the subset M. So let M be a set of external edges. A set of internal edges L is an M-completion just in case $M\cup L$ is a cycle cover of $G φ$ . Further, denote the set of all M-completions by $L M$ and the set of all resulting cycle covers of $G φ$ by $Z M$ .

Now, recall that construction of $G φ$ was such that each external edge had weight 1, so the weight of $Z M$ , the cycle covers resulting from any M, depends only on the internal edges involved. We add here the premise that the construction of the clause components is such that the sum over possible M-completions of the weight of the internal edges in each clause component, where M is proper relative to the clause component, is 12. Otherwise the weight of the internal edges is 0. (For now, we just specify this. Below, we give a reference to its proof.) Since there are m clause components, and the selection of sets of internal edges, L, within each clause component is independent of the selection of sets of internal edges in other clause components, so we can multiply everything to get the weight of $Z M$ . So the weight of each $Z M$ , where M induces a satisfying assignment, is $12 m$ . Further, where M does not induce a satisfying assignment, we know (from above) that M is not proper with respect to some $C j$ , so the product of the weights of internal edges in $Z M$ will be $0$ .

As for an explicit construction of the clause components, I suggest you believe they are simply magic. However, for the skeptic among you, the clause component is a weighted, directed graph with 7 nodes with edges weighted and nodes arranged to yield the properties specified above. The adjacency matrix A for this graph is given in Appendix A of Ben-Dor and Halevi (1993); checking that A has the necessary properties is left as an exercise for the interested reader. It is, however, important to note that the internal edges here have weights drawn from the set ${ - 1,0,1,2,3}$ , because in what follows we'll reduce our integer graph $G φ$ to a 01 graph. (This is important in understanding the necessity of the reductions below, because $G φ$ already seems to be a 01 graph if you only consider the external edges.)

Here, finally, we can get to the point of all this: since the sum of weights of all the sets of cycle covers inducing any particular satisfying assignment is $12 m$ , and the sum of weights of all other sets of cycle covers is 0, we have Perm( $G φ$ ) $= 12 m * S (φ)$ . Provided we can efficiently compute Perm( $G φ$ ) for our integer graph $G φ$ , our proof will be complete. The following section establishes the efficiency of this computation.

[edit] 01-Matrix

The above section has shown how to convert a 3-CNF formula into a directed weighted graph. Through a series of reductions, this graph can be turned into one that uses weights of only 0 or 1. The adjacency matrix of this graph has only elements of 0 or 1, and by computing its permanent, we can obtain the permanent of the original matrix easily.

[edit] Reduction to Non-Negatives

The objective is to convert an integer matrix $A$ into an equivalent non-negative matrix $A'$ so that the permanent of $A$ can be computed easily from the permanent of $A'$ . The idea is to use the modulo operator to convert an integer matrix into non-negative matrix. The complete construction is given below with a brief explanation for each step.

Let $A$ be an $n \times n$ integer matrix where no entry has a magnitude larger than $μ$ .

Compute $Q = 2 n! \cdot \mu^n + 1$ . The choice of Q is due to the fact that $|Perm(A)| \le n! \cdot \mu^n$
Compute $A' = A\,\bmod\,Q$
Compute $P = Perm(A')\,\bmod\,Q$
If $P < Q / 2$ then $P e r m (A) = P$ . Otherwise $P e r m (A) = P - Q$

The transformation of $A$ into $A'$ is polynomial in $n$ and $log(μ)$ , since the number of bits required to represent $Q$ is polynomial in $n$ and $log(μ)$

An example of the transformation and why it works is given below.

$A = \begin{bmatrix}2 & -2 \\ -2 & 1\end{bmatrix}$

$Perm(A) = 2 \cdot 1 + (-2) \cdot (-2) = 6$ .

Here, $n = 2$ , $μ = 2$ , and $μ n = 4$ , so $Q = 17$ . Thus

$A' = A\,\bmod\,17 = \begin{bmatrix}2 & 15 \\ 15 & 1\end{bmatrix}$

Note how the elements are non-negative because of the modular arithmetic. It is simple to compute the permanent

$Perm(A') = 2 \cdot 1 + 15 \cdot 15 = 227$

so $P = 227\,\bmod\,17 = 6$ . Then $P < Q / 2$ , so $P e r m (A) = P = 6$ .

[edit] Reduction to Powers of 2

The objective is to convert a non-negative matrix into an equivalent 2Powers matrix. Note that any number can be decomposed into a sum of powers of 2. For example,

13 = 2 3 + 2 2 + 2 0

This simple fact is used to convert a non-negative matrix into an equivalent 2Powers matrix. The reduction is performed on graphs which are equivalent to matrices.

Let $G$ be a $n$ -node weighted directed graph with non-negative weights, where largest weight is $W$ . Every edge $e$ with weight $w$ is converted into an equivalent edge with weights in powers of 2 as follows:

Failed to parse (Cannot write to or create math output directory): w = 2^{x_1} + 2^{x_2} + ... + 2^{x_r}

, $0 \le x_1 \le x_2 \le ... x_r \le \log (w)$

This can be seen graphically in the Figure 1. The subgraph that replaces the existing edge contains $r$ nodes and $3 r$ edges.

To prove that this produces an equivalent graph that has the same permanent as the original, we have to show the correspondence between the cycle covers of $G$ and $G'$ .

Consider some cycle-cover $R$ in $G$ .

If an edge $e$ is not in $R$ , then to cover all the nodes in the new sub graph, we have to use the self-loops. Since, all self-loops have a weight of 1, the weight of cycle-covers in $R$ and $R'$ match.
If $e$ is in $R$ , then in all the corresponding cycle-covers in $G'$ , there must a path from $u$ to $v$ , where u and v are the nodes of edge e. From the construction, we can see that there are $r$ different paths and sum of all these paths equal to the weight of the edge in the original graph $G$ . So the weight of corresponding cycle-covers in $G$ and $G'$ match.

Note that the size of $G'$ is polynomial in $n$ and $log W$

[edit] Reduction to 01

The objective here is to reduce a 2Powers matrix into an equivalent matrix containing only zeros and ones. (i.e. a directed graph where each edge has a weight of 1)

Let G be a n-node directed graph where all the weights on edges are powers of two. We must construct a graph, G', where the weight of each edge is 1 and Perm(G) = Perm(G'). The size of this new graph, G', is polynomial in the size of the graph G (which we defined to be n) and $p$ where the maximal weight of any edge in graph G is $2 p$ .

This reduction is done locally at each edge in G with a weight $> 1$ . Each such edge is replaced by a subgraph $J e$ and each edge in $J e$ has a weight of 1. Thus, the resulting graph, G', contains only edges with a weight of 1.

So, let $e = (u, v)$ be an edge in G with a weight $w = 2 r > 1$ . The new subgraph that we create, $J e$ is made up of $2 r$ nodes and $6 r$ edges as seen in Figure 2.

There are two cases for an original cycle cover $R$ in G.

If the original edge from graph G is not in the cycle cover on that graph, one cannot create a path through the new subgraph $J e$ . The only way to form a cover over $J e$ in such a case is for each node in the subgraph to take its cycle cover. As each edge has a weight of one, the weight of the resulting cycle cover is equal to that of the original cycle cover.

However, if the edge in G is a part of the cycle cover then there must be a path from $u$ to $v$ in the subgraph. At each step down the subgraph there are two choices one can make to form such a path. One must make this choice $r$ times, resulting in $2 r$ possible paths from $u$ to $v$ . Thus, there are $2 r$ possible cycle covers and since each path has a weight of 1, the sum of the weights of all these cycle covers equals the weight of the original cycle cover.

[edit] References

Ben-Dor, Amir and Halevi, Shai. (1993). "Zero-one permanent is #P-complete, a simpler proof". Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, 108-117.
Valiant, L.G. (1979). "The complexity of computing the permanent". Theoretical Computer Science 8, 189-201.
Jerrum, Sinclair, and Vigoda. (2001). "A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries". Theory of Computing, 712-721.

Categories: Computational complexity theory | Combinatorics