1
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Andy Drucker Aug 19 '13 at 20:10
-2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andy Drucker Aug 19 '13 at 20:09
  • $\begingroup$ @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. $\endgroup$ – Chad Brewbaker Aug 19 '13 at 20:30
  • $\begingroup$ "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. $\endgroup$ – Sasho Nikolov Aug 19 '13 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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