<p>Your problem is known to be NP-hard. See for instance</p>

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

CC BY-SA 4.0
2018-05-12T15:31:08.937Z
https://arxiv.org/abs/1512.01150v2
András Salamon
CC BY-SA 4.0
2018-05-12T15:05:55.017Z
2018-05-12T15:05:55.017Z
Gamow
<p>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.</p>

<p>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.</p>

<p>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$?</p>

<np-hardness><db.databases><boolean-matrix>
Minimum number of columns making each row different
defg
# Minimum number of columns making each row different

(Asked by: username_0 on 2018-05-11)

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$?

**Tags:** np-hardness, db.databases, boolean-matrix


---

## 1 answers

### Answer by username_1 on 2018-05-12. Score: 3

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).

> **Comments:**
> **username_2**: https://arxiv.org/abs/1512.01150v2  

---

