Consider we're given a set $S\subset \{0,1\}^n$ and we want to find a minimal subset $A \subset S$ under the property that if we bitwise OR all of the strings in $A$ we get the all ones string $1^n$. I have been having trouble finding a polynomial time algorithm for this or finding evidence that one doesn't exist (e.g.- by showing this problem to be NP-Complete). Does anyone have any ideas or references which may help answer my question?


1 Answer 1


This is the set cover problem, a well-known NP-complete problem, in disguise.

  • $\begingroup$ And here I was formulating it as an integer programming problem $\endgroup$
    – exfret
    Apr 11, 2018 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.