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?
Thanks in advance.