MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
+1. Very nice ! – Joel David Hamkins Jun 10 '10 at 18:28
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.