Algorithm to Determine if (Union of Cartesian Products of Subsets) equals (Cartesian Product of Full Sets)

Question

I have already asked this question in StackOverflow (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.

Answer 1

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.

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