ForgeGod

Constructing the Integer Graph

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

To specify $G_{\phi }$, we first note that for each of the n variables in $\phi$, there is a variable node in $G_{\phi }$. Additionally, for each of the m clauses in $\phi$, there is a clause component $C_{j}$ in $G_{\phi }$ that functions as a sort of "black box." For present purposes, all that needs to be noted about $C_{j}$ is that it has 3 input edges and 3 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, we have specified all of the nodes that will appear in the graph $G_{\phi }$.

Now for the edges. For each variable $x_{i}$ of $\phi$, we'll make a true cycle (T-cycle) and a false cycle (F-cycle) in $G_{\phi }$. 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 $\phi$ corresponding to $C_{j}$, this edge will be the first input edge of $C_{j}$, and so on. Thence, we draw an edge to the next clause component corresponding to the next clause of $\phi$ 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 or, alternatively, muggle edges, and all of them have weight 1. Inside the clause components, we term the edges internal edges or, alternatively, magical Leprechaun edges. We don't need to worry about their weights for now. Now, clearly, every muggle edge is part of a T-cycle or an F-cycle (but not both--that would require magic, or at least inconsistency).

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

A Very Nice Property of the Graph

Now, $G_{\phi }$ has the very nice property that its cycle covers correspond to variable assignments for $\phi$. This property is very nice because if I were you I'd be rather angry if I read this far and $G_{\phi }$ didn't have this property, and we can take it for granted that I'm not doing this just to make you angry. Unless you're a muggle. Anyway, for a cycle cover Z of $G_{\phi }$, we can say that Z induces an assignment of values for the variables in $\phi$ just in case Z contains all of the muggle edges in $x_{i}$'s T-cycle and none of the muggle 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 $\phi$, any one that does induces exactly one assignment, and the same assigment induced depends only on the muggle edges of Z.

The sort of Z's that don't induce assigments 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 $\phi$. This is because proper Z's contain either the complete T-cycle or the complete F-cycle of every variable $x_{i}$ in $\phi$ 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, 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.

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 muggle edges satisfied certain properties. Now for any cycle cover of $G_{\phi }$, we'll consider only its muggle edges, the subset M. So let M be a set of muggle edges. A set of Leprechaun edges L is an M-completion just in case $M\cup L$ is a cycle cover of $G_{\phi }$. Further, denote the set of all M-completions by $L^{M}$ and the set of all resulting cycle covers of $G_{\phi }$ by $Z^{M}$.

Now, recall that construction of $G_{\phi }$ was such that each muggle edge had weight 1, so the weight of $Z^{M}$, the cycle covers resulting from any M, depends only on the Leprechaun 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 Leprechaun edges in each clause component, where M is proper relative to the clause component, is 12. Otherwise the weight of the Leprechaun 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 Leprechaun edges, L, within each clause component is independent of the selection of sets of Leprechaun 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 Leprechuan 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 skeptical 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 a trivial exercise for the interested reader.

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

Invite

Gregbard 04:18, 14 July 2007 (UTC)

Thanks. Challenge accepted.ForgeGod (talk) 19:08, 17 May 2014 (UTC)

AfD nomination of Permanent is sharp-P-complete

An article that you have been involved in editing, Permanent is sharp-P-complete, has been listed for deletion. If you are interested in the deletion discussion, please participate by adding your comments at Wikipedia:Articles for deletion/Permanent is sharp-P-complete. Thank you. --Tznkai (talk) 19:10, 15 December 2008 (UTC)