polynomial-math - 我是多项式时间的子集求和算法吗？

Question

我想出了一个新算法来解决 subset sum problem ，我认为是多项式时间。告诉我我要么错了，要么就是个天才。

快速入门事实:

子集和问题是一个 NP 完全问题。在多项式时间内求解它意味着 P = NP。长度为 N 的集合中的子集数为 2^N。

更有用的是，长度为 N 的唯一子集的数量最大是整个集合的总和减去最小元素，或者，任何子集可能产生的总和范围介于所有负元素的总和之间以及所有正元素的总和，因为没有和可能大于或小于所有正或负和，当我们添加额外元素时，它们以线性速率增长。

这意味着随着 N 的增加，重复子集的数量呈指数增加，而唯一的、有用的子集的数量仅呈线性增加。如果可以设计出一种算法可以尽早删除重复的子集，我们将在多项式时间内运行。一个简单的例子很容易从二进制文件中获取。仅从 2 的幂的数字，我们可以为任何整数值创建唯一的子集。因此，任何涉及任何其他数字的子集(如果我们拥有 2 的所有幂)都是重复的和浪费的。通过不计算它们及其导数，我们几乎可以节省算法的所有运行时间，因为与任何整数相比，作为 2 的幂的数字是对数发生的。

因此，我提出了一个简单的算法，可以删除这些重复项并省去计算它们及其所有导数的麻烦。

首先，我们将对只有 O(N log N) 的集合进行排序，并将其分成正负两半。负数的过程是相同的，所以我只会概述正数(现在这个集合意味着只是正数，只是为了澄清)。

想象一个由 sum 索引的数组，它包含正侧的所有可能结果总和的条目(记住，这只是线性的)。当我们添加一个条目时，值是子集中的条目。所以，数组[3] = { 1, 2 }。

一般来说，我们现在开始枚举集合中的所有子集。我们通过从一个长度的子集开始，然后添加到它们来做到这一点。当我们拥有所有唯一的子集时，它们会形成一个数组，我们只需按照 Horowitz/Sahni 中使用的方式对它们进行迭代。

现在我们从“第一代”值开始。也就是说，如果原始数据集中没有重复的数字，则保证这些值中没有重复的数字。即所有单值子集，以及所有长度的集合减去一个长度的子集。这些可以通过对集合求和并依次减去每个元素来轻松生成。此外，集合本身是有效的第一代和和子集，以及子集的每个单独元素。

现在我们做第二代值。我们遍历数组中的每个值，对于每个唯一的子集，如果没有它，我们就添加它并计算新的唯一子集。如果我们有重复，就会产生乐趣。我们将其添加到碰撞列表中。当我们要添加新的子集时，我们会检查它们是否在碰撞列表中。我们通过不太理想的(通常更大，但可以是任意的)相等子集作为键。当我们添加到子集时，如果我们会产生碰撞，我们什么都不做。当我们要添加更理想的子集时，它会错过检查并添加，从而生成公共(public)子集。然后我们只是重复其他几代。

通过以这种方式删除重复的子集，我们不必继续将重复项与集合的其余部分组合，也不必继续检查它们是否存在冲突，也不必对它们求和。最重要的是，通过不创建非唯一的新子集，我们不会从中生成新的子集，我相信这可以将算法从 NP 变为 P，因为子集的增长不再是指数级的——我们丢弃它们中的绝大多数在下一代“繁殖”并通过与其他非重复子集组合来创建更多子集之前。

我认为我没有很好地解释这一点。我有照片……它们在我的脑海里。重要的是，通过丢弃重复的子集，您可以消除几乎所有的复杂性。

例如，想象一下(因为我是手工做这个例子的)一个简单的数据集，它从 -7 到 7(不是零)，我们的目标是零。排序和拆分，所以我们剩下 (1, 2, 3, 4, 5, 6, 7)。总和是 28。但是 2^7 是 128。所以 128 个子集适合范围 1 .. 28，这意味着我们事先知道 100 个集合是重复的。如果我们有 8 个，那么我们将只有 36 个插槽，但现在有 256 个子集。所以你可以很容易地看到，被骗的数量现在是 220，比以前多了一倍多。

在这种情况下，第一代值是 1, 2, 3, 4, 5, 6, 7, 28, 27, 26, 25, 24, 23, 22, 21，我们将它们映射到它们的组成成分，所以

1 = { 1 }
2 = { 2 }
...
28 = { 1, 2, 3, 4, 5, 6, 7 }
27 = { 2, 3, 4, 5, 6, 7 }
26 = { 1, 3, 4, 5, 6, 7 }
...
21 = { 1, 2, 3, 4, 5, 6 }

现在为了生成新的子集，我们依次取每个子集并将其添加到其他子集，除非它们有一个相互的子集，例如28和27有一个hueg相互子集。所以当我们取 1 并将它加到 2 时，我们得到 3 = { 1, 2 } 但是等等!它已经在数组中了。这意味着我们现在不向任何已经包含 2 的子集添加 1，反之亦然，因为这是 3 的子集的重复。

现在我们有

1 = { 1 }
2 = { 2 }
// Didn't add 1 to 2 to get 3 because that's a dupe
3 = { 3 } // Add 1 to 3, amagad, get a duplicate. Repeat the process.
4 = { 4 } // And again.
...
8 = { 1, 7 }

21? Already has 1 in.
...
27? We already have 28

现在我们全部加2。

1? Existing duplicate
3? Get a new duplicate
...
9 = { 2, 7 }
10 = { 1, 2, 7 }

21? Already has 2 in
...
26? Already have 28
27? Got 2 in already.

3？

1? Existing dupe
2? Existing dupe
4? New duplicate
5? New duplicate
6? New duplicate
7? New duplicate
11 = { 1, 3, 7 }
12 = { 2, 3, 7 }
13 = { 1, 2, 3, 7 }

如您所见，即使我每次仍在添加新的子集，数量也只会线性增加。

4？

1? Existing dupe
2? Existing dupe
3? Existing dupe
5? New duplicate
6? New duplicate
7? New duplicate
8? New duplicate
9? New duplicate
14 = {1, 2, 4, 7}
15 = {1, 3, 4, 7}
16 = {2, 3, 4, 7}
17 = {1, 2, 3, 4, 7}

5？

1,2,3,4 existing duplicate
6,7,8,9,10,11,12 new duplicate
18 = {1, 2, 3, 5, 7}
19 = {1, 2, 4, 5, 7}
20 = {1, 3, 4, 5, 7}
21 = new duplicate

现在我们有了范围内的所有值，所以我们停下来，将 1-28 添加到我们的列表中。对负数重复，遍历列表。

编辑:

这个算法在任何情况下都是完全错误的。具有重复和的子集不是重复的，因为子集可以从它们产生，因为它们的到达方式不同 - 即它们不能折叠。

Answer 1

这并不能证明 P = NP。

你没有考虑正数的可能性:1、2、4、8、16等......所以当你对子集求和时不会有重复，所以它会在 O(2^N) 中运行在这种情况下的时间。

您可以将此视为特殊情况，但对于其他类似情况，该算法仍然不是多项式。您所做的这个假设是您从子集总和的 NP 完全版本转向仅解决简单(多项式时间)问题的地方:

[assume the sum of the positive numbers grows] at a linear rate when we add extra elements.

在这里，您实际上是假设 P(即陈述问题所需的位数)小于 N。引自维基百科:

Thus, the problem is most difficult if N and P are of the same order.

如果您假设 N 和 P 具有相同的顺序，那么您不能假设随着添加更多元素，总和无限期地线性增长。当您向集合中添加更多元素时，这些元素也需要变大以确保问题仍然难以解决。

If P (the number of place values) is a small fixed number, then there are dynamic programming algorithms that can solve it exactly.

你重新发现了这些算法之一。这是一件不错的工作，但它不是什么新东西，也不能证明 P = NP。对不起!