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.