algorithm - 给定 m 个长度为 n 的位串，找出是否存在一组恰好 k 个位串使得在每个位置，只有 1 个位串有一个设置位

Question

太啰嗦了，让我解释一下。

假设我们有一组长度为 3 的 4 位串 -- {001, 100, 111, 010} 和 k = 3

这里的答案是 true 因为集合 {001, 100, 010} 在每个位置 {0 .. n - 1} code> 在位串中，只有一个位串有一个设置位。请注意，在所需的子集中，每个位置应该恰好有一个设置位。

另一个例子，考虑 {10001, 01000, 00110} 和 k = 3。这里的答案再次是 true。

如果 k = 2 则情况不同，因为我们希望所需集合的基数为 k。

Answer 1

这是 NP 难题，因为如果你能解决这个问题，那么你就可以解决 Exact set cover problem在多项式时间内。然而，已知精确集覆盖是 NP 完全的。