Is the "Fewest Discriminating Bits" problem NP-complete?

Question

That is a name I have made up for this problem. I have not seen it described anywhere before. I have not been able to find a proof of NP-completeness nor a polynomial time algorithm for this problem yet. It is not a homework problem -- it is related to a problem I have come across in my work.

FEWEST DISCRIMINATING BITS

INSTANCE: A set T containing bit vectors, where each bit vector is exactly N bits long. Every element of T is unique, as one would expect from a set in math. An integer K < N.

QUESTION: Is there a set B of at most K bit positions (i.e. integers in the range [0,N-1]) such that when we remove all bits except those in B from every vector in T, the remaining shorter vectors are all still unique?

Example 1: For the instance N=5, T={00010, 11010, 01101, 00011}, K=2, the answer is yes, because we can select the bit positions B={0,3}. Using the convention that bit position 0 is the rightmost, and the bit position numbers increase right-to-left, removing all bit positions except those in B from the vectors in T leaves T'={00, 10, 11, 01}, and those are all unique.

Example 2: N=5, T={00000, 00001, 00010, 00100}, K=2. The answer is no, because no matter which two bit positions we select, none of the 2-bit vectors will be equal to 11, so at least two of the 2-bit vectors will be equal to each other.

We can of course solve this problem by enumerating all (N choose K) subsets with size K of the N bit positions, and determining which satisfy the condition of the question. However, that is exponential in the input size.

Answer 1

This problem is NP-complete. A proof based on reduction from 3-SAT is as follows:

Consider an instance of 3-SAT with $n$ variables and $m$ clauses. We will construct $2n + 2m$ bit vectors ("rows") of length $2n + \lceil \log_2(n + m) \rceil$, such that the smallest number of discriminating bits is $n + \lceil \log_2(n + m) \rceil$ iff the original 3-SAT instance is satisfiable.

The first $2n$ bits will correspond to the literals $\left\{ x_1, \neg x_1, x_2, \neg x_2, ..., x_n, \neg x_n \right\}$. With respect to these bits, the first $2m$ rows will come in pairs, the first of which will have a $1$ for each literal included in the corresponding clause, and the second of which will consist entirely of $0$'s. The remaining $2n$ rows will also come in pairs, the first of which will have $1$'s for the corresponding literal and its negation, and the second of which will consist entirely of $0$'s. Finally, the last $\lceil \log_2(n + m) \rceil$ bits will be used to "sign" each pair of rows with its index, from $0$ to $n+m-1$, written in binary.

In order to distinguish each "literal" row from its successor, either the bit corresponding to that literal or the bit corresponding to its negation must be retained. Also, in order to discriminate among the $n+m$ "zero + index" rows, all $\lceil \log_2(n + m) \rceil$ index bits must be retained. The minimum possible number of discriminating bits is therefore $n + \lceil \log_2(n + m) \rceil$. Finally, in order to distinguish each "clause" row from its successor, at least one of the three bits corresponding to literals included in that clause must be retained. If the 3-SAT instance is satisfiable, this last condition will not require any extra bits (in particular, we do not need to retain the bits corresponding to both $x_i$ and $\neg x_i$ for any $i$); and conversely, if there are $n + \lceil \log_2(n + m) \rceil$ bits that discriminate among all $2n+2m$ bit vectors, they must contain exactly one of $x_i$ and $\neg x_i$ for each $i$, and hence correspond to a satisfying assignment of truth values to the $n$ variables.

Answer 2

Although a proof of NP-completeness is already provided, it might be worth pointing out that this problem is equivalent to a known NP-complete problem called the minimum test set problem ([SP6] in Garey and Johnson, also called the minimum test collection problem): just exchange the role of the sets and the role of the positions.