5
$\begingroup$

(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.

$\endgroup$
  • $\begingroup$ Note that the monoid in you motivating example is also idempotent (i.e. $x\circ x = x$ for all $x$), which could make for an interesting special case. $\endgroup$ – Klaus Draeger Nov 21 '15 at 22:23
1
$\begingroup$

L. J. Stockmeyer proves that SET BASIS is $\mathrm{NP}$-complete.

Reference: L.J. Stockmeyer, The set basis problem is $\mathrm{NP}$-complete, Tech. Report RC-5431, IBM, 1975

Each vector of your problem can be seen as subset of $\{1, 2, \dots, n\}$. And the component-wise OR operation is corresponding to set union. So a basis for a collection of Boolean vector in your problem is exactly a set basis.

$\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.