Although a [proof of NP-completeness](https://cstheory.stackexchange.com/questions/4304/is-the-fewest-discriminating-bits-problem-np-complete/4307#4307) 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](http://en.wikipedia.org/wiki/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness), also called the [minimum test collection problem](http://www.csc.kth.se/~viggo/wwwcompendium/node148.html)): just exchange the role of the sets and the role of the positions.