algorithm - 子集概率(同余变化)

Question

我想知道子集子问题变体的 NP 完备性:

子集和问题:给定一组整数和一个整数 s，是否任何非空子集总和为 s？

已知此问题属于 NP 问题并且是 NP 完全问题。现在考虑变化:

子集和问题(同余变化):给定两个整数 s 和 m 以及一组整数模 m，是否任何非空子集总和为 s mod m？

(即，集合中的所有数字都是模 m，预期和 s 也是模 m)。

我想知道以前是否研究过这个问题？ (想知道它是否是 NP 完全的)。有谁知道子集和问题是否有任何论文或类似的变体？谢谢!

Answer 1

是的，这个问题也是NP完全的。由于正常的子集和是NP完全的，因此将一些其他NP完全问题归约为子集和。

如果您可以另外生成一个足够大的模数，其大小为输入大小的多项式，则相同的归约也将用于证明模子集和是 NP 完全的。模数只要大于子集和解中使用的最大数即可，子集和与模子集和之差无关。

对于我能想到的任何归约，很容易产生这样的模数。请记住，只有模数的大小必须是输入大小的多项式，所以，假设 100^(N^2) 工作正常——它只是 2*(N^2)长数字。