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