<p>Simple observation, lets use {Animal}{Mineral}{Vegetable}</p>

<p>S = A,B,K = {horse,cat,dog}{gold,silver,quartz}{corn,tree, peach}</p>

<p>$S_{0}$ ={horse}{gold}{peach}</p>

<p>$S_{1}$ ={cat}{gold}{peach}</p>

<p>$S_{2}$ ={cat}{gold}{tree} ...</p>

<p>Your $n$ can be as big as $|A|$*$|B|$*$|C|$* ... *$|K|$. That's not tractable.</p>

<p>An adversary can just start generating you random elements in S. Kolomogrov complexity implies you will be forced to store them all without any compression until you get to that intractable number; making your storage intractable.</p>

CC BY-SA 3.0
2013-08-19T20:09:25.063Z
Just because the problem asks about an exponentially-sized search space, doesn't mean the problem is intractable.  Also, if you are given many random elements as part of the input, the budget of a polynomial-time algorithm increases accordingly (since the runtime is supposed to be polynomial in input length).  The problem stated is clearly in coNP, and so it is an open question in mathematics (equivalent to P vs NP) whether it can be solved efficiently.
Andy Drucker
CC BY-SA 3.0
2013-08-19T20:30:41.773Z
@Eduardo is asking for extreme compression. Going from the union of n expressions down to one without any guarantee of even getting compression from n-1 of them. If you can't compress tractably you can't solve tractably.
Chad Brewbaker
CC BY-SA 3.0
2013-08-19T21:57:16.983Z
"If you can't compress tractably you can't solve tractably." This statement requires proof. Especially if you are claiming something as strong as coNP \neq P.
Sasho Nikolov
CC BY-SA 3.0
2013-08-19T20:05:30.377Z
2013-08-19T20:05:30.377Z
Chad Brewbaker
<p>The problem is <strong>coNP</strong>-complete and so unlikely to have a poly-time algorithm.  (I'm sure the observation was made before; I don't know where, but look in Garey-Johnson.)</p>

<p>Here is a simple reduction from 3-UNSAT $= \{\psi: \psi$ is an unsatisfiable 3-CNF$\}$.</p>

<p>Say $\psi(x_1, \ldots, x_t) = \bigwedge_{j = 1}^m (y_{j, 1}\vee y_{j, 2} \vee y_{j, 3})$, where
each $y_{j, a}$ is either a variable or a negated variable.</p>

<p>In your notation, let $A = B = \ldots = K = \{0, 1\}$, with $t$ such sets (one for each variable).  Think of each element of $S = A^t$ as an assignment to $x_1, \ldots, x_t$.  For each $j \in [m]$, create a Cartesian product set $S_j$ which describes the set of assignments that will <em>falsify</em> the $j^{th}$ clause.  Note that this can easily be done: we restrict precisely the 3 components corresponding to the variables appearing in this clause.</p>

<p>The union of the $S_j$'s equals all of $S = \{0, 1\}^t$ iff every assignment to $\psi$ falsifies some clause, i.e., iff $\psi$ is unsatisfiable.</p>

CC BY-SA 3.0
2013-08-19T20:10:06.520Z
I forgot to say, it is easy to check whether some particular element is NOT in a given union of Cartesian products.  Thus the problem is in coNP.
Andy Drucker
CC BY-SA 3.0
2013-08-19T19:59:45.107Z
2013-08-19T19:59:45.107Z
Andy Drucker
<p>I have already asked this question in <a href="https://stackoverflow.com/questions/18281457/how-to-determine-if-union-of-cartesian-products-of-subsets-equals-cartesian-p">StackOverflow</a> (open bounty closing on Aug 25th).</p>

<p>Let's say I have some finite sets: A, B, ..., K</p>

<p>I also have A1, A2, ... An, which are subsets of A; B1, B2, ... Bn, which are subsets of B, etc.</p>

<p>Let's say S is the cartesian product A x B x ... x K</p>

<p>and Sn is the cartesian product of An x Bn x ... x Kn</p>

<p>Is there an algorithm to efficiently determine if the union of all <code>Sn</code> is equivalent to <code>S</code>?</p>

<p>Some pointers to literature where I can study this problem are greatly appreciated.</p>

<ds.algorithms>
Algorithm to Determine if (Union of Cartesian Products of Subsets) equals (Cartesian Product of Full Sets)
Eduardo
# Algorithm to Determine if (Union of Cartesian Products of Subsets) equals (Cartesian Product of Full Sets)

(Asked by: username_0 on 2013-08-19)

I have already asked this question in [StackOverflow](https://stackoverflow.com/questions/18281457/how-to-determine-if-union-of-cartesian-products-of-subsets-equals-cartesian-p) (open bounty closing on Aug 25th).

Let's say I have some finite sets: A, B, ..., K

I also have A1, A2, ... An, which are subsets of A; B1, B2, ... Bn, which are subsets of B, etc.

Let's say S is the cartesian product A x B x ... x K

and Sn is the cartesian product of An x Bn x ... x Kn

Is there an algorithm to efficiently determine if the union of all `Sn` is equivalent to `S`?

Some pointers to literature where I can study this problem are greatly appreciated.

**Tags:** ds.algorithms

---

## 2 answers

### Answer by username_2 on 2013-08-19. Score: 7 | Accepted answer

The problem is **coNP**-complete and so unlikely to have a poly-time algorithm. (I'm sure the observation was made before; I don't know where, but look in Garey-Johnson.)

Here is a simple reduction from 3-UNSAT $= \{\psi: \psi$ is an unsatisfiable 3-CNF$\}$.

Say $\psi(x\_1, \ldots, x\_t) = \bigwedge\_{j = 1}^m (y\_{j, 1}\vee y\_{j, 2} \vee y\_{j, 3})$, where
each $y\_{j, a}$ is either a variable or a negated variable.

In your notation, let $A = B = \ldots = K = \{0, 1\}$, with $t$ such sets (one for each variable). Think of each element of $S = A^t$ as an assignment to $x\_1, \ldots, x\_t$. For each $j \in [m]$, create a Cartesian product set $S\_j$ which describes the set of assignments that will *falsify* the $j^{th}$ clause. Note that this can easily be done: we restrict precisely the 3 components corresponding to the variables appearing in this clause.

The union of the $S\_j$'s equals all of $S = \{0, 1\}^t$ iff every assignment to $\psi$ falsifies some clause, i.e., iff $\psi$ is unsatisfiable.

> **Comments:**
> **username_2**: I forgot to say, it is easy to check whether some particular element is NOT in a given union of Cartesian products.  Thus the problem is in coNP.  

---

### Answer by username_1 on 2013-08-19. Score: -2

Simple observation, lets use {Animal}{Mineral}{Vegetable}

S = A,B,K = {horse,cat,dog}{gold,silver,quartz}{corn,tree, peach}

$S\_{0}$ ={horse}{gold}{peach}

$S\_{1}$ ={cat}{gold}{peach}

$S\_{2}$ ={cat}{gold}{tree} ...

Your $n$ can be as big as $|A|$\*$|B|$\*$|C|$\* ... \*$|K|$. That's not tractable.

An adversary can just start generating you random elements in S. Kolomogrov complexity implies you will be forced to store them all without any compression until you get to that intractable number; making your storage intractable.

> **Comments:**
> **username_2**: Just because the problem asks about an exponentially-sized search space, doesn't mean the problem is intractable.  Also, if you are given many random elements as part of the input, the budget of a polynomial-time algorithm increases accordingly (since the runtime is supposed to be polynomial in input length).  The problem stated is clearly in coNP, and so it is an open question in mathematics (equivalent to P vs NP) whether it can be solved efficiently.  
> **username_1**: @Eduardo is asking for extreme compression. Going from the union of n expressions down to one without any guarantee of even getting compression from n-1 of them. If you can't compress tractably you can't solve tractably.  
> **username_3**: "If you can't compress tractably you can't solve tractably." This statement requires proof. Especially if you are claiming something as strong as coNP \neq P.  

---

