找到一个与其他给定子集精确切割的子集是 NP 难的吗？
Is finding a subset with exact cut with other given subsets NP-hard?
我想弄清楚以下问题是否是 NP-hard:
Given G_1,..,G_n subsets of {1..m}
c_1,..,c_n non-negative integers in {0..m}
Find T subset of {1..m}
S.T. for all i=1..n, T intersects G_i in exactly c_i elements
我试图找到 coloring 等 NP 问题或 matching 等 P 问题的归约，但在这两种情况下都可以思考指数转换算法（即考虑大小为 c_i 的 G_i 的所有子集的算法），它不帮了我大忙 :(
旁注：对参数的任何限制都会使这个问题变得更容易吗？
例如，m<< n 是否会产生计算差异（我们仍然会寻找一种在 m 中为多项式的算法）？
如果我们知道某些常量 c_i 为零怎么办？
如有任何见解将不胜感激:)
这是 NP 完全问题，是 Hitting Set Problem 的推广。 NP 完整性证明如下。
问题出在 NP 中（微不足道 - 给定一个解决方案 T，很容易检查与每个 Gi 的交集，并验证其大小是否为 Ci）。
它也是 NP-Complete，假设您正在寻找 minimal 这样的 T，减少 Exact Hitting Set Problem:
精确命中集的判定问题为：
Given a universe of elements U, subsets S1,...,Sk, and a number
m - is there a subset S of U of size at most m that contains
exactly one element from each Si?
给定命中集问题实例 (S1,S2,...Sk,d) - 用 Gi=Si, ci = 1 将其简化为这个问题，如果这个问题的最小解的大小为 d，还有一个精确命中大小 d 的解决方案（反之亦然）。
我想弄清楚以下问题是否是 NP-hard:
Given G_1,..,G_n subsets of {1..m}
c_1,..,c_n non-negative integers in {0..m}
Find T subset of {1..m}
S.T. for all i=1..n, T intersects G_i in exactly c_i elements
我试图找到 coloring 等 NP 问题或 matching 等 P 问题的归约，但在这两种情况下都可以思考指数转换算法（即考虑大小为 c_i 的 G_i 的所有子集的算法），它不帮了我大忙 :(
旁注：对参数的任何限制都会使这个问题变得更容易吗？
例如，m<< n 是否会产生计算差异（我们仍然会寻找一种在 m 中为多项式的算法）？
如果我们知道某些常量 c_i 为零怎么办？
如有任何见解将不胜感激:)
这是 NP 完全问题，是 Hitting Set Problem 的推广。 NP 完整性证明如下。
问题出在 NP 中（微不足道 - 给定一个解决方案 T，很容易检查与每个 Gi 的交集，并验证其大小是否为 Ci）。
它也是 NP-Complete，假设您正在寻找 minimal 这样的 T，减少 Exact Hitting Set Problem:
精确命中集的判定问题为：
Given a universe of elements
U, subsetsS1,...,Sk, and a numberm- is there a subsetSofUof size at mostmthat contains exactly one element from eachSi?
给定命中集问题实例 (S1,S2,...Sk,d) - 用 Gi=Si, ci = 1 将其简化为这个问题，如果这个问题的最小解的大小为 d，还有一个精确命中大小 d 的解决方案（反之亦然）。