Decomposition of a true / false vector into its parts

Question

I am wondering if this is a common computer science problem and is there any polynomial workaround or approximation

Suppose I have a list X consisting of true and false values

X = [True, False, True, False, True...True] 

I also have a set of other lists that are the same length as X, with true and false values

 A = [False, True, True, True, True, False .... False] B = [False, False, True, False, True, False .... False] ...etc 

Now I want to find the “sum” of these other lists (which applies the bitwise OR operator to each element, i.e. F + F = F, F + T = T, T + T = T), which is best to explain the observations that are visible in list X (I can imagine a scoring system that gives some score for a match and a penalty for inconsistency in the decision), and since there can be many possible solutions, I want to impose a penalty on the algorithm for more lists that it uses in its decision.

Answer 1

The problem you are describing is NP-hard by reducing the problem of the minimum cover problem , which is known to be NP-hard.

The abbreviation is as follows. For a set S of n elements, create a list of n copies of "true" as your list X. Then for each set that can be resolved in the cover of the set, replace it with a list that has true or false in each place based on whether the set does not contain this element S. If you assign a penalty for infinity to a discrepancy and assign a cost of one for each list, then in the original there is an installed cover of size k or less, set a cover problem if and only if your problem has a solution of cost k and and less.

This means that there is no known polynomial time algorithm for this problem, and you need to either take rough answers or wish your program to last a long time on some inputs.

Hope this helps!