如何确定（子集的笛卡尔积并集）是否等于（全集的笛卡尔积）

Question

假设我有一些有限集合：A，B，...，K 我还有A1，A2，... An是A的子集；B1，B2，... Bn是B的子集等等。

假设S是笛卡尔积A x B x ... x K 而Sn是An x Bn x ... x Kn的笛卡尔积

是否有一种有效的算法可以确定所有Sn的并集是否等于S？

编辑

我也在Theoretical Computer Science论坛上问了这个问题。一个答案证明了该问题是coNP完全的。如果答案的作者想在这里发布答案，我会保持问题开放以授予悬赏。

- Eduardo

---

你如何定义这里的效率？检查AxBx...xK中的每个项目是否可接受，还是乘积太大了？ - Michael

@Michael：计算所有组合需要太多时间。在现实生活中，集合的数量和每个集合中的元素数量几乎是无限的。 - Eduardo

我写了一个不错的回答，但是发现在CSTheory上已经有类似的回答由[Andy Drucker]发布。我建议关闭此问题。 - tom

@tom：是的，我昨天也在那里发布了这个问题。我想保持这个问题的开放性，以便在安迪·德鲁克（Andy Drucker）在这里发布他的答案后能够授予赏金。 - Eduardo

@Eduardo 好的，如果他没有回复，我会发布我的答案。 - tom

Answer 1

问题是coNP-Complete，因此没有有效算法可以解决它。

我将展示3SAT可以归约到这个问题的补集（检查所有S_i的并集是否不等于S）。

考虑具有变量a，b，...，k和布尔公式的3SAT问题

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

c_i = x_i,1 ∨ x_i,2 ∨ x_i,3 而x_i,j是一个文字（变量或变量的否定）。

将A = B = C = ... = K设置为{true，false}。

将A_i设置为

• { false } 如果 c_i 包含变量 a
• { true } 如果 c_i 包含变量 a 的否定
• { true, false } 如果 c_i 不提及 a

对于所有 1 ≤ i ≤ n，B_i 到 K_i 同样如此。

任何元组 (a, b, ..., k) ∈ S_i = A_i ⨯ B_i ⨯ ... ⨯ K_i 都不会满足 c_i，因为 c_i 中的所有文字都将被否定。

考虑元组 (a, b, ..., k) ∈ S₁ ⋃ S₂ ⋃ ... ⋃ S_n。这些元组至少属于一个 S_i，因此它们不会满足 c_i，因此也无法满足 f。

如果 S₁ ⋃ S₂ ⋃ ... ⋃ S_n 等于 S = A ⨯ B ⨯ ... ⨯ K，则所有元组都不满足 f，因此 f 不可满足。同样可以证明，如果并集不等于 S，则存在一个元组满足 f。

因此，3SAT 可以归约到原问题的补集。但是，原问题的补集属于 NP，因为测试给定元组是否不在并集中可以在多项式时间内完成。因此，原问题的补集是 NP-完全的，原问题本身是 coNP-完全的。

- tom

Answer 2

我不知道是否有可能高效地完成此操作。但是，通过逐步检查越来越大的集合，如果答案是否定的话，在实践中可以提前退出：

• 每个集合 A1，...，An 的并集应为 A
• 每对集合 A x B 的并集 A1 x B1，...，An x Bn 应为 A x B
• 对于三元组等集合重复上述步骤

思考更多后，我认为这似乎不能在不检查 S 的每个元素的情况下完全检查。考虑以下实例：

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

所有 Sn 的并集是 S - (a1, b1, c1)。从给定的子集中似乎很难检测到这一点，除非明确检查 (a1, b1, c1)。

- Mangara

---

感谢您的输入。S - (a1，b1，c1)确实很棘手。如果有算法可以做到这一点，我想它必须将Sn分成更简单、更可组合的项。 - Eduardo