<p>You are looking for the shortest straight-line program to compute a set of formulas involving xor.</p>

<p>This is NP-hard. There are papers on how to efficiently solve this problem with  SAT solver. For example, Fuhs and Schneider-Kamp had this recent paper on <a href="http://www0.cs.ucl.ac.uk/staff/C.Fuhs/papers/SAT10-slp.pdf" rel="nofollow">Synthesizing Shortest Linear Straight-Line
Programs over GF(2) using SAT</a>.</p>

<p>There is a proof that this problem is MAXSNP-hard by Boyar, Matthews and Peralta, see <a href="http://link.springer.com/article/10.1007%2Fs00145-012-9124-7" rel="nofollow">here</a>.</p>

CC BY-SA 3.0
2014-12-07T22:44:54.933Z
The paper you linked indeed _states_ that the problem is known to be MaxSNP-hard, but it does not give any reference.  Do you have one?
Tsuyoshi Ito
CC BY-SA 3.0
2014-12-07T22:57:51.030Z
Good call, updated with a reference.
Chao Xu
CC BY-SA 3.0
2014-12-24T15:32:30.413Z
Too bad Fuhs and Schneider-Kamp haven't published the software/method they used to generate the input to the SAT programs. Going from a linear form to the propositional logic isn't trivial, for me at least.
I think I will use the heuristic in the paper by Boyar, Matthews and Peralta for now.
Thom Wiggers
CC BY-SA 3.0
2014-12-07T21:48:05.610Z
2014-12-07T22:57:31.710Z
2014-12-07T22:57:31.710Z
Chao Xu
<p>It seems the following algorithm gives you the optimal procedure:</p>

<p>Your memory is a set of current targets $t_1,\dots t_k$ together with a set of partial products $p_1,\dots, p_n$ initally empty. Additionally, each partial product is marked by a subset of $\{1,k\}$, which is the set of current targets which strictly contain this product.</p>

<ol>
<li>For each letter, count in how many of the targets it appears. Let $a$ be the letter appearing in the maximal number of targets.</li>
<li>Add $a$ to all partial products that point at one of these targets, producing new partial products. If some target containing $a$ was not marked by any partial product, create a new partial product with $a$.</li>
<li>Update targets containing $a$ by removing one occurrence of it.</li>
<li>Update the marking of the partial products.</li>
</ol>

<p>Loop these steps until all your targets are empty.</p>

<p>You should end up with the minimal set of partial products you need to compute.</p>

<p>Notice that this algorithm produces an optimal output, but may not be optimal in complexity.</p>

CC BY-SA 3.0
2014-12-03T15:47:59.090Z
This seems promising. A bad complexity is ok, the result is only used to help me write faster assembly code.
Thom Wiggers
CC BY-SA 3.0
2014-12-03T15:51:22.993Z
Yes I got the impression this was the spirit of your question.
Denis
CC BY-SA 3.0
2014-12-03T17:08:33.943Z
I'm having a bit of trouble with the generation of (new) partial products and the adding of `a` to partial products. If I generate all possible partial products, how can I end up with the minimal set? How are possibilities eliminated?
Thom Wiggers
CC BY-SA 3.0
2014-12-04T12:38:35.000Z
You don't general them all, only those who are reached by this order. Run the algorithm on your example, you will see that the only partial product of length $2$ generated is $bc$.
Denis
CC BY-SA 3.0
2014-12-04T12:46:53.300Z
How would $\{p_1, \cdots, p_n\}$ be initialised then?
Thom Wiggers
CC BY-SA 3.0
2014-12-04T13:03:40.167Z
at the beginning you have only the empty product. It's true that I was not precise with the status of empty product...
Denis
CC BY-SA 3.0
2014-12-04T13:05:49.847Z
Wouldn't that mean that at step 2 there are no products pointing at targets, thus nothing happening?
Thom Wiggers
CC BY-SA 3.0
2014-12-04T13:07:17.830Z
More precisely at the beginning your set of partial products is empty. Then every time you process a letter, if some target $i$ where it appears was not marked by any partial product, then you add the single letter $a$ as a new partial product. (I edit the answer)
Denis
CC BY-SA 3.0
2014-12-07T13:53:36.070Z
If I remove $a$ from all targets, wouldn't step 4 ensure that all partial products generated or modified in step 2 immediately get unlinked from all targets (because the products now contain $a$ and because of step 4, $\forall t, a \not\in t$ anymore)?
Thom Wiggers
CC BY-SA 3.0
2014-12-07T21:08:23.540Z
No you just remove one occurence of $a$ in each target, some targets can have more than one $a$
Denis
CC BY-SA 3.0
2014-12-15T22:00:51.767Z
Unless I'm thinking of something else, no they can't. It's an XOR, so more than two $a$'s in a target would cancel each other out.
Thom Wiggers
CC BY-SA 3.0
2014-12-16T14:38:25.377Z
ah indeed, this algorithm is for more general purpose, if you know it is a XOR it gets much simpler.
Denis
CC BY-SA 3.0
2014-12-03T15:45:13.007Z
2014-12-04T13:09:36.113Z
2014-12-04T13:09:36.113Z
Denis
<p>I'm implementing an encryption algorithm which does a bunch <code>xor</code> operations to mix up the columns. Because I want to find the lower bound of the number of <code>xor</code> operations, I'm trying to figure out the best way to reuse intermediate results. I've created a graph with all the intermediate results and now want to find the paths through that graph that reuse the most nodes.</p>

<p><strong>Simplified example:</strong> I want to calculate $abc$ and $bcd$ from $a,b,c,d$. I can only combine two variables at a time. Combining is commutative: the order does not matter. I've created a graph with all the possible intermediate results ($ab, bc, cd$). Obviously the best way to calculate $abc$ and $bcd$ is to do it like $abc = a (bc)$ and $bcd = d (bc)$. This way you can reuse the result of $bc$ and you end up doing 3 operations, instead of the 4 operations if you would do something like $abc = (ab)c$ and $bcd = (bc)d$.</p>

<p>In other words, I want fo find these paths:</p>

<pre><code>       abc         bcd
        |           |
  +-----+--+--------+
  |        |        |
  | ab     bc   cd  |
  |        |        |
  |      +-+-+      |
  |      |   |      |
  a      b   c      d
</code></pre>

<p>Is there an algorithm suitable for finding this, or is there an algorithm that I can adapt to find this? (If there is an approach that doesn't use graphs, I'd like to learn of it as well).</p>

<p><strong>Actual problem:</strong>
I have 16 inputs $x_0 \cdots x_{15}$ which are <code>xor</code>ed like this:</p>

<p>$$
\begin{array}{rcl}
x_0 &amp;=&amp; x_0 \oplus x_4 \oplus x_7 \oplus x_{10} \oplus x_{12} \oplus x_{14} \oplus x_{15} \\
x_{1} &amp;=&amp; x_1 \oplus x_4 \oplus x_{11} \oplus x_{12} \oplus x_{15} \\
x_{2} &amp;=&amp; x_2 \oplus x_5 \oplus x_8 \oplus x_9 \oplus x_{12} \\
x_{3} &amp;=&amp; x_3 \oplus x_6 \oplus x_9 \oplus x_{10} \oplus x_{13} \\
x_{4} &amp;=&amp; x_0 \oplus x_3 \oplus x_4 \oplus x_8 \oplus x_{10} \oplus x_{11} \oplus x_{14} \\
x_{5} &amp;=&amp; x_0 \oplus x_5 \oplus x_8 \oplus x_{11} \oplus x_{15} \\
x_{6} &amp;=&amp; x_1 \oplus x_6 \oplus x_8 \oplus x_{12} \oplus x_{13} \\
x_{7} &amp;=&amp; x_2 \oplus x_7 \oplus x_9 \oplus x_{13} \oplus x_{14} \\
x_{8} &amp;=&amp; x_2 \oplus x_4 \oplus x_6 \oplus x_7 \oplus x_8 \oplus x_{12} \oplus x_{15} \\
x_{9} &amp;=&amp; x_3 \oplus x_4 \oplus x_7 \oplus x_9 \oplus x_{12} \\
x_{10} &amp;=&amp; x_0 \oplus x_1 \oplus x_4 \oplus x_{10} \oplus x_{13} \\
x_{11} &amp;=&amp; x_1 \oplus x_2 \oplus x_5 \oplus x_{11} \oplus x_{14} \\
x_{12} &amp;=&amp; x_0 \oplus x_2 \oplus x_3 \oplus x_6 \oplus x_8 \oplus x_{11} \oplus x_{12} \\
x_{13} &amp;=&amp; x_0 \oplus x_3 \oplus x_7 \oplus x_8 \oplus x_{13} \\
x_{14} &amp;=&amp; x_0 \oplus x_4 \oplus x_5 \oplus x_9 \oplus x_{14} \\
x_{15} &amp;=&amp; x_1 \oplus x_5 \oplus x_6 \oplus x_{10} \oplus x_{15} \\
\end{array}
$$</p>

<p>I want to find groups such as $\{x_0, x_4\}$, $\{x_1, x_4\}$ and $\{x_{0}, x_{4}, x_{10}\}$ that are contained in several of these multiplications.</p>

CC BY-SA 3.0
2014-12-03T14:10:59.117Z
What you are asking is likely not what you want. Why exclude cancellations?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-12-03T14:12:27.617Z
What do you mean by cancellations? $a \oplus b \oplus a = b$?
Thom Wiggers
CC BY-SA 3.0
2014-12-03T15:31:30.887Z
since it is commutative, it seems it suffices to take the intersection of the multiset of letter used, at least in the case where you have $2$ outputs to compute. If you have more, it requires more thinking.
Denis
CC BY-SA 3.0
2014-12-03T15:39:26.187Z
I have 16 outputs, so yeah.
Thom Wiggers
<graph-algorithms><optimization>
Finding the paths through a graph that reuse as many of the nodes as possible
Thom Wiggers
# Finding the paths through a graph that reuse as many of the nodes as possible

(Asked by: username_0 on 2014-12-03)

I'm implementing an encryption algorithm which does a bunch xor operations to mix up the columns. Because I want to find the lower bound of the number of xor operations, I'm trying to figure out the best way to reuse intermediate results. I've created a graph with all the intermediate results and now want to find the paths through that graph that reuse the most nodes.
Simplified example: I want to calculate $abc$ and $bcd$ from $a,b,c,d$. I can only combine two variables at a time. Combining is commutative: the order does not matter. I've created a graph with all the possible intermediate results ($ab, bc, cd$). Obviously the best way to calculate $abc$ and $bcd$ is to do it like $abc = a (bc)$ and $bcd = d (bc)$. This way you can reuse the result of $bc$ and you end up doing 3 operations, instead of the 4 operations if you would do something like $abc = (ab)c$ and $bcd = (bc)d$.
In other words, I want fo find these paths:
       abc         bcd
        |           |
  +-----+--+--------+
  |        |        |
  | ab     bc   cd  |
  |        |        |
  |      +-+-+      |
  |      |   |      |
  a      b   c      d

Is there an algorithm suitable for finding this, or is there an algorithm that I can adapt to find this? (If there is an approach that doesn't use graphs, I'd like to learn of it as well).
Actual problem:
I have 16 inputs $x_0 \cdots x_{15}$ which are xored like this:
$$
\begin{array}{rcl}
x_0 &=& x_0 \oplus x_4 \oplus x_7 \oplus x_{10} \oplus x_{12} \oplus x_{14} \oplus x_{15} \\
x_{1} &=& x_1 \oplus x_4 \oplus x_{11} \oplus x_{12} \oplus x_{15} \\
x_{2} &=& x_2 \oplus x_5 \oplus x_8 \oplus x_9 \oplus x_{12} \\
x_{3} &=& x_3 \oplus x_6 \oplus x_9 \oplus x_{10} \oplus x_{13} \\
x_{4} &=& x_0 \oplus x_3 \oplus x_4 \oplus x_8 \oplus x_{10} \oplus x_{11} \oplus x_{14} \\
x_{5} &=& x_0 \oplus x_5 \oplus x_8 \oplus x_{11} \oplus x_{15} \\
x_{6} &=& x_1 \oplus x_6 \oplus x_8 \oplus x_{12} \oplus x_{13} \\
x_{7} &=& x_2 \oplus x_7 \oplus x_9 \oplus x_{13} \oplus x_{14} \\
x_{8} &=& x_2 \oplus x_4 \oplus x_6 \oplus x_7 \oplus x_8 \oplus x_{12} \oplus x_{15} \\
x_{9} &=& x_3 \oplus x_4 \oplus x_7 \oplus x_9 \oplus x_{12} \\
x_{10} &=& x_0 \oplus x_1 \oplus x_4 \oplus x_{10} \oplus x_{13} \\
x_{11} &=& x_1 \oplus x_2 \oplus x_5 \oplus x_{11} \oplus x_{14} \\
x_{12} &=& x_0 \oplus x_2 \oplus x_3 \oplus x_6 \oplus x_8 \oplus x_{11} \oplus x_{12} \\
x_{13} &=& x_0 \oplus x_3 \oplus x_7 \oplus x_8 \oplus x_{13} \\
x_{14} &=& x_0 \oplus x_4 \oplus x_5 \oplus x_9 \oplus x_{14} \\
x_{15} &=& x_1 \oplus x_5 \oplus x_6 \oplus x_{10} \oplus x_{15} \\
\end{array}
$$
I want to find groups such as $\{x_0, x_4\}$, $\{x_1, x_4\}$ and $\{x_{0}, x_{4}, x_{10}\}$ that are contained in several of these multiplications.

**Tags:** graph-algorithms, optimization

> **Comments:**
> **username_1**: What you are asking is likely not what you want. Why exclude cancellations?  
> **username_0**: What do you mean by cancellations? $a \oplus b \oplus a = b$?  
> **username_2**: since it is commutative, it seems it suffices to take the intersection of the multiset of letter used, at least in the case where you have $2$ outputs to compute. If you have more, it requires more thinking.  
> **username_0**: I have 16 outputs, so yeah.  

---

## 2 answers

### Answer by username_3 on 2014-12-07. Score: 3 | Accepted answer

You are looking for the shortest straight-line program to compute a set of formulas involving xor.

This is NP-hard. There are papers on how to efficiently solve this problem with SAT solver. For example, Fuhs and Schneider-Kamp had this recent paper on [Synthesizing Shortest Linear Straight-Line
Programs over GF(2) using SAT](http://www0.cs.ucl.ac.uk/staff/C.Fuhs/papers/SAT10-slp.pdf).

There is a proof that this problem is MAXSNP-hard by Boyar, Matthews and Peralta, see [here](http://link.springer.com/article/10.1007%2Fs00145-012-9124-7).

> **Comments:**
> **username_4**: The paper you linked indeed _states_ that the problem is known to be MaxSNP-hard, but it does not give any reference.  Do you have one?  
> **username_3**: Good call, updated with a reference.  
> **username_0**: Too bad Fuhs and Schneider-Kamp haven't published the software/method they used to generate the input to the SAT programs. Going from a linear form to the propositional logic isn't trivial, for me at least. I think I will use the heuristic in the paper by Boyar, Matthews and Peralta for now.  

---

### Answer by username_2 on 2014-12-03. Score: 0

It seems the following algorithm gives you the optimal procedure:

Your memory is a set of current targets $t\_1,\dots t\_k$ together with a set of partial products $p\_1,\dots, p\_n$ initally empty. Additionally, each partial product is marked by a subset of $\{1,k\}$, which is the set of current targets which strictly contain this product.

1. For each letter, count in how many of the targets it appears. Let $a$ be the letter appearing in the maximal number of targets.
2. Add $a$ to all partial products that point at one of these targets, producing new partial products. If some target containing $a$ was not marked by any partial product, create a new partial product with $a$.
3. Update targets containing $a$ by removing one occurrence of it.
4. Update the marking of the partial products.

Loop these steps until all your targets are empty.

You should end up with the minimal set of partial products you need to compute.

Notice that this algorithm produces an optimal output, but may not be optimal in complexity.

> **Comments:**
> **username_0**: This seems promising. A bad complexity is ok, the result is only used to help me write faster assembly code.  
> **username_2**: Yes I got the impression this was the spirit of your question.  
> **username_0**: I'm having a bit of trouble with the generation of (new) partial products and the adding of `a` to partial products. If I generate all possible partial products, how can I end up with the minimal set? How are possibilities eliminated?  
> **username_2**: You don't general them all, only those who are reached by this order. Run the algorithm on your example, you will see that the only partial product of length $2$ generated is $bc$.  
> **username_0**: How would $\{p_1, \cdots, p_n\}$ be initialised then?  
> **username_2**: at the beginning you have only the empty product. It's true that I was not precise with the status of empty product...  
> **username_0**: Wouldn't that mean that at step 2 there are no products pointing at targets, thus nothing happening?  
> **username_2**: More precisely at the beginning your set of partial products is empty. Then every time you process a letter, if some target $i$ where it appears was not marked by any partial product, then you add the single letter $a$ as a new partial product. (I edit the answer)  
> **username_0**: If I remove $a$ from all targets, wouldn't step 4 ensure that all partial products generated or modified in step 2 immediately get unlinked from all targets (because the products now contain $a$ and because of step 4, $\forall t, a \not\in t$ anymore)?  
> **username_2**: No you just remove one occurence of $a$ in each target, some targets can have more than one $a$  
> **username_0**: Unless I'm thinking of something else, no they can't. It's an XOR, so more than two $a$'s in a target would cancel each other out.  
> **username_2**: ah indeed, this algorithm is for more general purpose, if you know it is a XOR it gets much simpler.  

---

