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