Return to Question

(At the very bottom of this, I will shortly describe the motivation for this question.)

Assume we have a commutative monoid $(G,\circ)$, i.e. a set $G$ with a commutative binary operation $\circ$ that satisfies associativity and the existence of a neutral element. The task is as follows: given some $X \subseteq G$, find $\text{argmin}_{U \subseteq G} \{|U| : X \subseteq \langle U \rangle\}$ where $\langle U \rangle$ is the submonoid generated by the elements of $U$. Thus, we want a smallest $U$ such that $\langle U \rangle$ covers $X$.

Now, if instead of a monoid we had a vector space, the task would be simple: determine the subspace spanned by $X$, and find a base for it. However, this relies on vectors having inverses, which we can't assume to exist in our monoid.

The monoid can be assumed to be fixed, i.e. we don't have to receive it as input, and the only input we receive is $X$. To be more precise, the set $G$ can implicitly be assumed to be $\{0,1\}^n$ for some $n$, and $\circ$ is the component-wise $\max$ operation, which is the same as $\{\text{true}, \text{false}\}^n$ with component-wise $\text{OR}$.

As an example, assume $n=4$ and we want to cover $$X= \{(0,1,0,1), (1,1,0,0),(1,0,1,0),(1,1,0,1),(1,1,1,1)\}$$

then one optimal solution would be $\{(0,1,0,1), (1,0,1,0), (1,1,0,0)\}$.

Question: what is the complexity of this problem? I have a feeling it's somewhere between a covering problem and a hull problem, but I can't quite put my finger on whether I've come across a variant of this before or not.

The problem arose when a colleague of mine played around with a building block used in LED clocks. They have the structure

 _
|_|
|_|

and each of those seven lines has its own control wire. We only want to use $10$ of the possible $2^7$ configurations of those control wires, so we tried to figure out whether we can build all $10$ configurations using less than $7$ primitives via OR-ing. Since OR over binary vectors doesn't come with inverses, we only have a monoid.

(At the very bottom of this, I will shortly describe the motivation for this question.)

Assume we have a commutative monoid $(G,\circ)$, i.e. a set $G$ with a commutative binary operation $\circ$ that satisfies associativity and the existence of a neutral element. The task is as follows: given some $X \subseteq G$, find a smallest $U \subseteq G$ such that $X \subseteq \langle U \rangle$, where $\langle U \rangle$ is the submonoid generated by the elements of $U$.

Now, if instead of a monoid we had a vector space, the task would be simple: determine the subspace spanned by $X$, and find a base for it. However, this relies on vectors having inverses, which we can't assume to exist in our monoid.

The monoid can be assumed to be fixed, i.e. we don't have to receive it as input, and the only input we receive is $X$. To be more precise, the set $G$ can implicitly be assumed to be $\{0,1\}^n$ for some $n$, and $\circ$ is the component-wise $\max$ operation, which is the same as $\{\text{true}, \text{false}\}^n$ with component-wise $\text{OR}$.

As an example, assume $n=4$ and we want to cover $$X= \{(0,1,0,1), (1,1,0,0),(1,0,1,0),(1,1,0,1),(1,1,1,1)\}$$

then one optimal solution would be $\{(0,1,0,1), (1,0,1,0), (1,1,0,0)\}$.

Question: what is the complexity of this problem? I have a feeling it's somewhere between a covering problem and a hull problem, but I can't quite put my finger on whether I've come across a variant of this before or not.

The problem arose when a colleague of mine played around with a building block used in LED clocks. They have the structure

 _
|_|
|_|

and each of those seven lines has its own control wire. We only want to use $10$ of the possible $2^7$ configurations of those control wires, so we tried to figure out whether we can build all $10$ configurations using less than $7$ primitives via OR-ing. Since OR over binary vectors doesn't come with inverses, we only have a monoid.