Wednesday, March 2, 2011

Dependent Variables

Let's talk a little about XOR clauses. If you have a variable that appears in a single XOR we can remove that clause because it always can be satisfied by setting the proper value of the chosen variable. Let's call this variable dependent. I was reading Mate Soos's paper on Gaussian Elimination and he suggested that we can apply a similar technique for variables that appear in two XOR clauses. These variables, called mutexes, are very common when splitting long XOR clauses before transforming them in CNF clauses.

For example: \begin{align*} a+b+c+d+e+f & = 1 \\ \text{can be split into} \\ a+b+c+z & = 0 \\ z+d+e+f & = 1 \end{align*} with $z$ being a mutex.

I think that dependent variables can be generalized further for all variables that appears only in XOR clauses. Let $u$ be such a variable. Since a XOR clause is actually a equation in $G_2$ we use the shortest XOR clause containing $u$ to knock out $u$ from all other XOR clauses containing $u$ as in Gaussian Elimination. Now u appears in a single XOR clause and therefore it can be removed.together with the clause. I wonder if anybody else thought of this.

Update: Here is a graph showing the performance improvement of Dependent Variable Elimination. On one instance the speed improvement was almost 200 fold. That's impressive. Of course, the instances without XOR gates were not affected.

1 comment:

1. The report supplies an correct evaluation of the altering aggressive dynamics. It supplies a forward-looking perspective on the varied components that drive or limit market development. It supplies a Portable Washers and Dryers five-year forecast evaluated primarily based on SLS 3D Printing Service market development projections. Helps in understanding the important thing} product segments and their future, to achieve a complete view of the market, and make knowledgeable enterprise choices by performing an in-depth evaluation of the market segments. Metal or cement additionally be|may also be|can be} used to create solid objects via 3D printing. Thousands of companies use Gelato’s software and APIs to provide and ship customized printed products anywhere on the earth.