17
$\begingroup$

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

$\endgroup$

1 Answer 1

18
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$ Aug 13, 2015 at 21:38
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 15, 2015 at 20:54

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.