I have two disjoint sets $X$, $Y$, of length-$n$ bitstrings.
For a set $P\subset\{0,1,2,...n-1\}$ and a bitstring $b$, let $b_P$ be the string obtained by taking only those elements of $b$ who's index is in $P$ (in increasing order of index).
Now define $X_P=\{b_P \mid b \in X \}$ and $Y_P=\{b_P \mid b \in Y \}$ .
A set $P$ is "valid" if $X_P$ and $Y_P$ are also disjoint. The problem is determining (at least one of) the valid sets $P$ of minimum cardinality (among the possible valid sets), for the given $X$ and $Y$.
For example, if $X=\{1001,1000\}$ and $Y=\{0001\}$, there is only one valid set of minimum cardinality, namely $P=\{0\}$ . We have $X_{P}=\{1\}$ and $Y_{P}=\{0\}$ .
Another way of putting the problem is, given two disjoint sets of bit-strings, which bits must be read from an element of their union to decide whether it's a member of one set or the other?
Does there exist a known algoritm for this problem? Is the complexity bad?