2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

See this paper and this paper.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.