Is the "Fewest Discriminating Bits" problem NP-complete?
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.