6

假设我有一些有限集：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？

编辑

我也在理论计算机科学论坛上问过这个问题。答案证明问题是 coNP 完全的。如果答案的作者想在此处发布，我将保持问题悬而未决以奖励赏金。

4

2 回答 2

3

这个问题是conNP-Complete，所以没有有效的算法来解决它。

我将证明3SAT可以简化为这个问题的补集（检查所有 S i的并集是否不等于 S）。

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

        f = c 1 ∧ c 2 ∧ ... ∧ 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 1 ⋃ S 2 ⋃ ... ⋃ S n。这些元组至少属于一个 S i，因此它们不会满足 c i，因此不能满足 f。

如果 S 1 ⋃ S 2 ⋃ ... ⋃ S n等于 S = A ⨯ B ⨯ ... ⨯ K，则所有元组都不满足 f，因此 f 不可满足。可以类似地证明，如果并集不等于 S，则存在一个满足 f 的元组。

所以 3SAT 可以简化为原问题的补集。但是原始问题的补码在 NP 中，因为可以在多项式时间内完成对给定元组是否不在联合中的测试。所以原问题的补是NP-Complete，而原问题本身是coNP-Complete。

于 2013-08-20T07:00:00.317 回答
1

我不知道是否可以有效地做到这一点。但是，通过逐步检查更大的集合，如果答案是否定的，实际上可以提前退出：

  • 的并集A1, ..., An应该是A每个集合
  • 的并集A1 x B1, ..., An x Bn应该是A x B每对集合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).

于 2013-08-16T23:41:41.337 回答