Set cover by alternative of sets
That is tightly equivalent to CNF-SAT.



CNF-SAT ​ $\to$ ​ your problem ​ ​ ​ :

The subscripts are the variables and the superscripts indicate whether the

literal is positive or negative. ​ ​ ​ If you want to preserve the number of solutions, then insert

clauses of the form ​ x or not x ​ for each variable x. ​ ​ ​ Other than that, the elements are

the clauses, and each set is the set of clauses in which the corresponding literal occurs.

your problem ​ $\to$ ​ CNF-SAT ​ ​ ​ :

There is one variable per pair-of-sets, and one clause per element.

For each element x and variable i, ​ ​ ​ ​ ​ ​ ​ not i ​ is in x's clause if and only if x is in $S^i_0$ ​ ​ ​ 

and ​ ​ ​ (the positive literal) i ​ is in x's clause if and only if x is in $S^i_1$ ​ ​ ​ .