Algorithm - minimal number of bits to distinguish a set of given binary numbers

Question

Say that we are given K different binary numbers, each with length N (N can be large). Is there an efficient algorithm to determine the minimal number of bits it needs to distinguish these numbers from each other?

For example:

Given 110 and 011, we only have to check the first (or the last) bit to distinguish them, so the minimal number is 1.

Given 1000, 0100, 0010 and 0001, we need to check at least three bits to distinguish, so the minimal number is 3.

Given 0000, 0100, 1000 and 1100, we only have to check the first two bits, so the minimal number is 2.

Follow-up: output the corresponding indexes to be checked.

---

Edit: Assuming these binary numbers are represented as a1[0,1,…,N-1], …, aK[0,1,…,N-1]. This problem is equivalent to finding the minimal subsequence [i,j,…,m] of [0,1,…,N-1] so that a1[i,j,…,m], …, aK[i,j,…,m] are different numbers.

Answer 1

The Set Cover is defined in terms of a set U, and a set S of subsets of U. Each element in U must be covered by (at least) one of the sets in S.

If you can solve Set Cover, you can solve this problem as well. Suppose you build a set U whose each entry, u_{i, j} (where i < j), corresponds to the pairs (i, j) and (j, i) of your k numbers (hence |U| = k (k - 1) /2). Now build n sets, S₁, ..., S_n, corresponding to the n possible bit positions. Set S_j is the subset of all the elements corresponding to pairs position j differentiates. That is, if numbers k, l are different in position j, then set u_{k, l} &in; S_j.

As such, the simple greedy algorithm for set cover, can give you an bounded approximation of the minimal number of bits. Unfortunately, it will not give you the minimal number of bits. As noted by @augurar in the comments, this problem is NP-Hard by reduction, and, as such, probably does not have a feasible exact optimal algorithm.