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

Question

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?

EDIT

I have also asked this question in the Theoretical Computer Science forum. An answer proves that the problem is coNP-complete. I am keeping the question open to award the bounty if the author of the answer wants to post it here.

Answer 1

The problem is coNP-Complete, so there is no efficient algorithm to solve it.

I will show that 3SAT can be reduced to the complement of this problem (checking if the union of all S_i is not equal to S).

Consider the 3SAT problem with variables a, b, ..., k and Boolean formula

        f = c₁ ∧ c₂ ∧ ... ∧ c_n

where

        c_i = x_i,1 ∨ x_i,2 ∨ x_i,3

and x_i,j is a literal (either a variable or the negation of a variable).

Set A = B = C = ... = K = { true, false }.

Set A_i to

• { false } if c_i contains the variable a
• { true } if c_i contains the negation of variable a
• { true, false } if c_i does not mention a

and similarly for B_i through K_i for all 1 ≤ i ≤ n.

Any tuple (a, b, ..., k) ∈ S_i = A_i ⨯ B_i ⨯ ... ⨯ K_i will not satisfy c_i since all the literals in c_i will be negated.

Consider the tuples (a, b, ..., k) ∈ S₁ ⋃ S₂ ⋃ ... ⋃ S_n. These tuples belong to at least one S_i so they will not satisfy c_i and therefore fail to satisfy f.

If S₁ ⋃ S₂ ⋃ ... ⋃ S_n is equal to S = A ⨯ B ⨯ ... ⨯ K, all the tuples fail to satisfy f and so f is unsatisfiable. It can be similarly shown that if the union is not equal to S there exists a tuple which satisfies f.

So 3SAT can be reduced to the complement of the original problem. But the complement of the original problem is in NP, because testing if a given tuple is not in the union can be done in polynomial time. So the complement of the original problem is NP-Complete, and the original problem itself is coNP-Complete.

Answer 2

I don't know if it is possible to do this efficiently. However, by checking progressively larger sets of sets, it would be possible in practice to bail out early if the answer is no:

• The union of A1, ..., An should be A for each set
• The union of A1 x B1, ..., An x Bn should be A x B for each pair of sets A x B
• Repeat for triples, etc. of sets

Thinking more about it, it seems unlikely to me that this can be checked fully without checking every element of S. Consider the following instance:

A = {a1, a2, a3}  B = {b1, b2, b3}  C = {c1, c2, c3}

A1 = A         B1 = B         C1 = {c2, c3}
A2 = A         B2 = {b2, b3}  C2 = C
A3 = {a2, a3}  B3 = B         C3 = C

Here the union of all Sn is S - (a1, b1, c1). This seems hard to detect from the given subsets without explicitely checking for (a1, b1, c1).