# poly-time algorithm to choose elements of sets

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.

• This sounds related to 3 dimensional matching, an NP hard problem. Perhaps someone can post a reduction of 3DM or nDM to this problem? Gerhard "Ask Me About System Design" Paseman, 2010.06.10 – Gerhard Paseman Jun 10 '10 at 18:09
• This rather sounds like reducing 3SAT to me. – darij grinberg Jun 10 '10 at 18:15
• I added the complexity-theory and NP tags. – Joel David Hamkins Jun 10 '10 at 20:29

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).

• But perhaps you should use 3-SAT or other bounded size disjunctions, to avoid the blow-up in size that comes from taking all nonempty subsets for $B_i$? – Joel David Hamkins Jun 10 '10 at 18:29
• Thanks. In fact I intuitively perceived the size of the clauses to be "really small" compared to their number ;) – darij grinberg Jun 10 '10 at 18:38
• Yes, I think this is required, since otherwise you won't have a polynomial reduction. – Joel David Hamkins Jun 10 '10 at 20:13
• Thanks to everybod and particularly to Darij for the reduction from SAT. Not quite what I had hoped for, but at least I now know that there "no" hope for a polynomial-time algorithm. – simone Jun 11 '10 at 10:51