Return to Revisions

It seems to me that your problem is stronger than $\ell$-SAT. In fact, let $A$ be the set of our literals. Assume that we have $p$ clauses. For each $i\in\left\lbrace 1,2,...,p\right\rbrace$, let $A_i$ be the set of the literals occuring in the $i$-th clause, and let $B_i$ be the set of all nonempty subsets of $A_i$. Besides, add some more sets $A_{p+1}$, $A_{p+2}$, ..., $A_i$ which are of the form {literal, its negation}, and for every such sets $A_k$, let $B_k$ be the set of its 1-element subsets. I think that a choice of $C_i$ is the same as a satisfaction of all our clauses (the elements of $C_1\cup C_2\cup ...\cup C_k$ corresponding to those literals that are satisfied).