# Minimize the sum of components of a hypercube under a system of $0,1$ equations.

Let $$x_1, \dots, x_5, y_1, \dots, y_4$$ be a total of nine variables taking values merely in $$\{0, 1\} \subset \Bbb{Z}$$. Therefore a solution is a point on a hypercube.

These are the constraint equations: $$x_1 + x_2 + y_1 + y_2 = 1 \\ x_2 + x_3 + y_1 + y_2 + y_3 = 1 \\ x_3 + x_4 + y_2 + y_3 + y_4 = 1 \\ x_4 + x_5 + y_3 + y_4 = 1$$

That I want to solve, while at the same time minimizing (something like): $$x_1 + \dots + x_5 + y_1 + \dots + y_4$$

The system alone can be solved in terms of 5 parameters in $$\{0, 1\}$$. That's $$2^5$$ possibilities to check in the naive worst case. This generalizes therefore not to a polynomial time algorithm.

Can we make use of symmetry somehow since the 1st and the last constraint equation are essentially the same. I don't know how to formally make use of that symmetry though...

Thus, how do I minimize the sum of the components of the hypercube under more variables than equations, in polynomial time with respect to $$n$$ the number of variables?

I can't think of any more constraints to my problem, but the problem this corresponds to is computing at least one smallest grammar of $$s = aaaaaa$$. Symmetries here are obvious since $$Aaaaa$$ and $$aaaaA$$ would be two distinct choices in an algorithm that are actually symmetric, so that you can skip one.

The constraint equations can be derived for example by noting that $$x_i \in \{0, 1\}$$ is whether the $$i$$th occurence of $$aa$$ within $$s$$ (starting from the left), and if it's present, it cancels out the presence of the 2nd $$aa$$ since they intersect. $$y_i$$ is whether the $$i$$th occurence of $$aaa$$ is present. By present I mean in a general grammar for $$s$$ that a solution then describes.

• I think this is a no-go approach. Working on a better idea now. – EnjoysMath Aug 2 '19 at 4:21

This is an instance of SET COVER, which is NP-complete. But with this structured version, you can pick $$y_{2+3k}$$ and then if that doesn't cover everything then one of the $$x_j$$ will cover the remaining one or two constraints.