Skip to main content
Added complexity-theory and NP tags
Link
Joel David Hamkins
  • 236.4k
  • 44
  • 777
  • 1.4k
Source Link

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.