1
$\begingroup$

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.

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

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.

$\endgroup$

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.