Minimum number of columns making each row different I'm curious whether this problem is NP-hard: suppose you are given an arbitrary $m\times n$ 0-1 matrix (each element is either 0 or 1, for the simplicity of the problem), and any pair of rows (i.e. a 0-1 vector of dimension-$n$) are different (in other words, there are no repetitive rows). I'd like to select a minimum number of columns such that each row within these columns are different.

To make sure you understand it correctly, there is a firm lower bound, $\log_2m$, of the number of columns to be selected, but you don't know whether a solution of size $\log_2m$ exists. In addition, there must be a feasible solution of size $n$ since each row is different.

Is there an efficient algorithm for solving this? Or I need to solve it in a brute-forth way by checking every possible combinations of columns from $\log_2m$ to $n$?
Your problem is known to be NP-hard. See for instance


  Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge:
  "Exploiting hidden structure in selecting dimensions that distinguish vectors."
  Journal of Computer and System Sciences 82, pp 521-535 (2016).