Suppose you receive a list of $n$ instructions on $k$ boolean variables where each instruction has the form

$$x_i \leftarrow x_i \oplus x_j,$$

(where $\oplus$ is the binary XOR) can we efficiently find a minimal series of instructions (of the same form) that computes the same result, using up to $m$ initially zero extra temporaries?

  • 1
    $\begingroup$ Do you mean that in the end all values of $x_i$ must be the same as after the original set of instructions? I mean, if we want only one value in the end, it'll make the problem trivial (just count the parity of inputs in the final expression). $\endgroup$ – Dmitry Jul 29 '20 at 11:34
  • $\begingroup$ @Dmitry The set of instructions when executed can be seen as a function $f : \{0,1\}^n \to \{0,1\}^n$. Can we efficiently find a smaller set of instructions, forming function $g : \{0,1\}^n \to \{0,1\}^n$ such that $\forall \mathbf{x} (f(\mathbf{x}) = g(\mathbf{x}))$? That is my question, with the addition of allowing some temporary variables for $g$ as well (which are initially zero and ignored for the output). Note that sometimes even without temporaries you can already do better. $\endgroup$ – orlp Jul 29 '20 at 12:49
  • $\begingroup$ Each instruction can be described as a linear map in $\mathbb_2{F}$, so the overall series of instructions is one binary matrix, with AND and XOR as multiplication and addition respectively. Is this efficient enough? $\endgroup$ – Richie Yeung Jul 29 '20 at 12:57
  • 1
    $\begingroup$ Your type of program is known as a "linear circuit", see e.g. www3.nd.edu/~jhauenst/preprints/ghilRigidity.pdf. One usually allows more complicated instructions (XOR of several arguments), but the complexity measure is the total number of operands ("edges"). I expect minimizing such circuits to be hard. In your case you also have a bound on the memory; I'm not sure this has been considered in this context (but does appear in related computation models such as branching programs, as the "width" of the program). $\endgroup$ – Yuval Filmus Jul 29 '20 at 13:30
  • 2
    $\begingroup$ @YuvalFilmus I guess this proof also applies, for sufficiently large $m$? cstheory.stackexchange.com/questions/32267/… $\endgroup$ – orlp Jul 29 '20 at 13:38

I don't know what sort of efficiency you are looking for, it would be good if you clarified it.

Each instruction can be described as a linear map in $\mathbb{F}_2$, so the overall series of instructions is one linear map.

As for finding the minimal set of instructions, given a limited number of temporary variables, I believe this is analogous to the register allocation problem for compilers, which is NP-COMPLETE.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.