4
$\begingroup$

Given a set of $n$ binary strings of length $m$, how many binary strings at least should we add to the set to make sure that the binary "AND" and "OR" operators are closed on the set? The output of the problem is the number of binary strings needed to add.

For example, given the set {001, 010, 110}, we should at least add {000, 011, 111} to the set to make both "AND" and "OR" operators closed. So the output is 3.

Is there any good algorithm or idea related to the problem? Thanks a lot.

  • 1
    You could repeatedly add "AND" and "OR" of strings you already have. This will certainly terminate, because your strings have a certain length. Now try to optimize this approach.2011-05-20
  • 0
    But how to optimize it?2011-05-20

2 Answers 2