# Best known algorithm for a common problem.

I am looking for the best known algorithm for the following problem: Input: Matrix M with R rows and C cols and values true-false in each position Output: Minimum number of cols such that the OR operation between all selected cols results in R trues.

I think another form of this problem is: Given C numbers of N bits, get the minimum amount of numbers needed to sum 2^N - 1.

In case this is NP-Complete, then does someone know where can I find the reduction? And is there any pseudo-polynomial algorithm? Maybe using dynamic programming on some bounded variable?

The universe $\mathcal{U}$ corresponds to the rows of the matrix $M$, and each member of $\mathcal{S}$ corresponds to each column. The entry $m_{i,j}$ is true if and only if the $i$-th element of $\mathcal{U}$ belongs to the $j$-th member of $\mathcal{S}$.