# Uniquely identifying bits

Query: Given $$m$$ unique integers smaller than $$2^n$$, can we keep at most $$k$$ the same bits of each number to uniquely identify them?

Is this problem NP-Hard?

For example, given the $$4$$ unique numbers smaller than $$2^3$$

011
100
101
110
^^


The numbers are still unique if we remove the leftmost bit from each number. So for $$k = 2$$, the answer is yes: we keep bits {0, 1} (the rightmost bit is here defined as the bit with index 0).

I want to solve the above problem as a precomputation step for integers less than 20 bits, so for my application an exponential algorithms could be allowed. Then it would be great to minimize $$k$$ and then break ties in such a way that the number of gaps between the indices that are kept is minimized. For example, {0, 1, 2, 5, 7} has two gaps: between 2 and 5 and between 5 and 7. This precomputation should lead to a great hash function for a set of integers. In my application the sets of integers don't change later.

Your problem is NP-hard. To see this, you can reduce it from the minimum test cover (or test collection) problem: given a set $$X$$ of $$\ell$$ elements and a collection $$C = \{C_1, \dots, C_k \}$$ of $$k$$ subsets of $$X$$, find a minimum test cover for $$X$$ and $$C$$, i.e., a subset $$C'$$ of $$C$$ that has minimum size and satisfies the following property: for every pair of distinct elements $$i,j \in X$$ there is a set in $$C'$$ that contains exactly one of $$i$$ and $$j$$.
The reduction is as follows: for each element $$x \in X$$ create a number of $$k$$ bits $$b_1,\dots,b_k$$ where $$b_i = 1$$ if and only if $$x \in C_i$$. There is a test-cover $$C' = \{ C_{i_1}, C_{i_2}, \dots \}$$ if and only if the $$|C'|$$ bits in positions $$i_1, i_2, \dots$$ suffice to distinguish all input numbers.
Since the above reduction sets $$m=\ell$$, the measures for two corresponding solutions of test-cover and your problem coincide, and test cover is not approximable within a factor of $$o(\log \ell)$$, this also shows that your problem is $$o(\log m)$$-inapproximable.
On the bright side, the converse reduction works too: given an instance of your problem you can create an instance of minimum test cover by considering the set $$X$$ containing your $$\ell = m$$ input numbers $$x_1, \dots, x_m$$ and $$C = \{C_1, \dots, C_k \}$$ as a collection of $$k = n$$ sets where $$C_i = \{ x \in X \mid \text{the i-th bit of x is } 1 \}$$. This means that the $$O(\log \ell)$$-approximation algorithm for minimum test-cover immediately translates to a $$O(\log m)$$-approximation algorithm for your problem.