CODEWITHSUNDEEP
algorithmsetcartesian-product
Eduardo
Eduardo

Reputation: 8402

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

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.

Upvotes: 6

Views: 1599

Answers (2)

tom
tom

Reputation: 22989

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 Si is not equal to S).

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

        f = c1 ∧ c2 ∧ ... ∧ cn

where

        ci = xi,1 ∨ xi,2 ∨ xi,3

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

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

Set Ai to

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

and similarly for Bi through Ki for all 1 ≤ i ≤ n.

Any tuple (a, b, ..., k) ∈ Si = Ai ⨯ Bi ⨯ ... ⨯ Ki will not satisfy ci since all the literals in ci will be negated.

Consider the tuples (a, b, ..., k) ∈ S1 ⋃ S2 ⋃ ... ⋃ Sn. These tuples belong to at least one Si so they will not satisfy ci and therefore fail to satisfy f.

If S1 ⋃ S2 ⋃ ... ⋃ Sn 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.

Upvotes: 3

Mangara
Mangara

Reputation: 1146

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

Upvotes: 1

Related Questions