Finding a minimal subset of strings whose bitwise OR is the all ones string 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?
This is the set cover problem, a well-known NP-complete problem, in disguise.