Edu*_*rdo 6 algorithm set cartesian-product
假设我有一些有限集: A, B, ..., K
我也有A1, A2, ... AnA的子集; B1, B2, ... Bn这是B等的子集
让我们说S是笛卡尔积A x B x ... x K
并且Sn是笛卡儿的产品An x Bn x ... x Kn
有没有一种算法可以有效地确定所有联合Sn是否相等S？
编辑
我也在理论计算机科学论坛上问了这个问题.答案证明问题是完全可靠的.如果答案的作者想在这里发布,我仍然可以提出问题以奖励赏金.
该问题是coNP-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设置为
对于 B i到 K i也同样，对于所有 1 ≤ i ≤ n。
任何元组 (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，因此它们不会满足ci ，因此无法满足f 。
如果 S 1 ⋃ S 2 ⋃ ... ⋃ S n等于 S = A ⨯ B ⨯ ... ⨯ K，则所有元组都不能满足 f，因此 f 不可满足。类似地可以证明，如果并集不等于S，则存在满足f的元组。
所以3SAT可以简化为原问题的补集。但原始问题的补集是 NP 问题，因为测试给定元组是否不在并集中可以在多项式时间内完成。所以原问题的补集是NP-Complete，原问题本身是coNP-Complete。