子集问题在 Wikipedia 中定义如下：
给定一组整数，是否存在总和为零的非空子集？例如，给定集合 { -7, -3, -2, 5, 8}，答案是肯定的，因为子集 { -3, -2, 5} 的总和为零。
或者
给定一组整数和一个整数 s，是否有任何非空子集和 s？
这个问题的蛮力解决方案是指数的（循环遍历 N 个数字的所有子集，并且对于每个子集，检查子集的总和是否为正确的数字），还有一些针对在指数时间内运行的蛮力的优化版本。
假设有一种算法可以在二次和多项式时间复杂度之间计算蛮力解决方案（上述问题的精确解决方案）
它如何被认为与 P=NP 问题、时间复杂度等有关？
假设存在算法，是否会改进子集和问题的最新技术？
（我不是这方面的专家，所以如果有些事情没有意义或不清楚，我会在力所能及的范围内为这个问题提供额外的输入:)）
由于子集问题是NP完全的，如果你能找到问题的多项式时间解，那么你可以在多项式时间内解决NP中的所有问题，并且P = NP。
现在，如果不了解什么是 NP 和 NP 完全性，上述陈述当然是没有意义的。定义 NP 问题的方法有很多种，但最简单的方法是当且仅当存在可以在多项式时间内检查其解的正确性的验证者时，问题才属于 NP。在子集和问题的情况下，显然您可以在多项式时间内验证其解。因此，这是一个NP问题。
NP-complete 类是 NP 中的一组特殊问题，因此 NP 中的所有问题都可以在多项式时间内简化为 NP-complete 中的任何问题。例如，Cook 证明的第一个 NP 完全问题是 SAT 问题，您尝试确定是否存在对一组布尔变量的可能分配，以便布尔公式评估为真。通过正确的过程，您可以在多项式时间内将 NP 中的所有决策问题转换为 SAT，这使得 SAT NP 完全。您可以在此处找到有关原始证明的更多详细信息，但这需要对图灵机有所了解。
为了证明新问题的 NP 完全性，您可以尝试将现有的 NP 完全问题简化为新问题。例如，我们知道 SAT 问题可以很容易地简化为 3-SAT 问题。这意味着给定一个 SAT 问题，我们可以将其转换为 3-SAT 版本，这样解决等效的 3-SAT 问题就可以得到原始 SAT 问题的结果。由于 NP 中的所有问题都可以归结为 SAT，并且 SAT 可以归结为 3-SAT，这使得 3-SAT 问题 NP-complete。
这是一个很好的证明，说明如何将 3-SAT 简化为子集和问题。作为证明的结果，子集和问题是NP完全的。因此，如果您可以找到子集和问题的多项式时间解，那么您可以在多项式时间内解决所有 NP 问题（是的，包括旅行商、图形着色、背包等问题）（因为所有归约都是在多项式时间内完成）。