17

Suppose we are given a set of n boolean variables x_1,...,x_n and a set of m functions y_1...y_m where each y_i is the XOR of a (given) subset of these variables. The goal is to compute the minimum number of XOR operations you need to perform to compute all these y_1...y_m functions.

Note that the result of an XOR operation, say x_1 XOR x_2 might be used in computation of multiple y_j's but is counted as one. Also, note that it might be useful to compute XOR of a much larger collection of x_i's (larger than any y_i function, e.g. computing XOR of all x_i's) in order to compute y_i's more efficiently,

Equivalently, suppose we have a binary matrix A, and a vector X and the goal is to compute vector Y such that A.X=Y where all operations done in GF(2) using minimum number of operations.

Even when each row of A has exactly k one's (say k=3) is interesting. Does anybody know about the complexity (hardness of approximation) for this question?

Mohammad Salavatiopur

Mohammad R. Salavatipour
  • 173
  • 4

1 Answers1

18

This is NP-hard. See: Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. http://link.springer.com/article/10.1007/s00145-012-9124-7

The reduction is from Vertex Cover and is very nice.

Given a graph $(\{1,\ldots,n\},E)$ with $m=|E|$, define an $m \times (n+1)$ matrix $A$ as: $A[i,j] = 1$ if $j < n+1$ and $(i,j) \in E$, and $A[i,n+1] = 1$. In other words, given $n+1$ variables $x_1,\ldots,x_{n+1}$ we want to compute the $m$ linear forms $x_i+x_j+x_{n+1}$ for all $(i,j) \in E$.

A little thought shows that there is an XOR circuit for $A$ with gates of fan-in two computing the linear transformation $A$ with only $m+k$ gates, where $k$ is the optimal vertex cover for the graph. (First compute $x_{i'} + x_{n+1}$ for all $i'$ in the vertex cover, using $k$ operations. The linear forms are then all computable in $m$ more operations.) It turns out that this is also a minimum size circuit!

The proof that the reduction is correct is not so nice. I would love to see a short proof that this reduction is correct.

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164
  • Thanks Ryan. Very relevant paper indeed. I thought whether the problem could be as hard as vertex-cover in hypergraphs at least for the case you are not to generate larger XOR sums (what is referred to cancellation-free in this paper I think). – Mohammad R. Salavatipour Aug 13 '15 at 21:38
  • 3
    For the cancellation-free case, the NP-hardness is noted in Garey-Johnson under the somewhat obscure name "Ensemble Computation" (Problem PO9, in A11.1). The reduction is actually same as the one outlined by Ryan, see Section 3.2.2 in G-J. – Janne H. Korhonen Aug 15 '15 at 20:54