User talk:ForgeGod

From Wikipedia, the free encyclopedia

[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 φ. We'll construct a weighted, directed graph G_φ such that (1) each satisfying assignment for φ will have a corresponding cycle cover in G_φ where the sum of the weights of each cycle cover 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 note that for each of the n variables in φ, there is a variable node in G_φ. Additionally, for each of the m clauses in φ, there 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 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_φ.

Now for the edges. For each variable x_i of φ, we'll 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, we 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 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_φ 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 φ. This property is very nice because if I were you I'd be rather angry if I read this far and G_φ 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_φ, we can say that Z induces an assignment of values for the variables in φ 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 φ, 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 φ. 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, 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 muggle edges satisfied certain properties. Now for any cycle cover of G_φ, 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 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 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_φ) = 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.