Let $A\_1,A\_2,\ldots,A\_k$ be finite sets. Furthermore, for each $i\in\{1,2,\ldots,k\}$, let $B\_i$ be a set whose elements are subsets of $A\_i$. 


Is there any polynomial-time algorithm that decides whether there exists a choice of precisely one element $C\_i$ of each $B\_i$ such that for all $x\in (C\_1\cup C\_2\cup\ldots\cup C\_k)$ the following property is satisfied: 


If $x\in A\_i$ then $x\in C\_i$ for each $i\in\{1,2,\ldots,k\}$?


Any pointer to a paper etc. would be greatly appreciated. Thanks.



poly-time algorithm to choose elements of sets
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).


