# time complexity – Calculating minimal discriminator of a set of columns in a matrix with unique rows

Having a matrix $$M$$, with unique rows, how to calculate a minimal subset of colums $$D$$ such that every row is unique? Also, how to maximize the amount of unique rows, if the number of chosen columns is limited?

For example:

$$M$$ =

``````0 0 0 0 0 1
0 0 0 0 0 2
0 0 0 1 0 0
0 0 0 2 0 0
``````

$$D$$ (columns {4, 6} from $$M$$) =

``````0 1
0 2
1 0
2 0
``````

It seemed like a Bounded Knapsack Problem at first, but the weights of each item in knapsack depends on other items, so it’s not a classical knapsack problem.

Is there a known solution for this problem?