2
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 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$
    – user114966
    Commented Jul 29, 2020 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
    Commented Jul 29, 2020 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
    Commented Jul 29, 2020 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
    Commented Jul 29, 2020 at 13:30
  • 3
    $\begingroup$ @YuvalFilmus I guess this proof also applies, for sufficiently large $m$? cstheory.stackexchange.com/questions/32267/… $\endgroup$
    – orlp
    Commented Jul 29, 2020 at 13:38

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Minimal number of instructions, no ? $\endgroup$
    – user16034
    Commented Aug 14, 2023 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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