我的多项式时间的子集和算法？

Question

我想出了一个新算法来解决子集求和问题,我认为它是在多项式时间内.告诉我,我要么是错的,要么是天才.

快速启动事实:

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

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

这意味着当N增加时,重复子集的数量呈指数增长,并且唯一有用子集的数量仅线性增加.如果可以设计出可以尽早移除重复子集的算法,我们将在多项式时间运行.一个简单的例子很容易从二进制中获取.仅从2的幂的数字,我们可以为任何积分值创建唯一的子集.因此,任何涉及任何其他数字的子集(如果我们拥有所有权力的两个)都是重复和浪费.通过不计算它们及其衍生物,我们几乎可以节省算法的所有运行时间,因为与任何整数相比,2的幂的数字是对数发生的.

因此,我提出了一个简单的算法,它将删除这些重复项,并节省必须计算它们及其所有衍生物.

首先,我们将对仅为O(N log N)的集合进行排序,并将其分为两半,正面和负面.负数的程序是相同的,所以我只勾勒出正数(现在的数字只是正半数,只是为了澄清).

想象一下由sum索引的数组,其中包含正面所有可能结果总和的条目(只记住线性,记住).添加条目时,该值是子集中的条目.就像,array [3] = {1,2}.

通常,我们现在移动到枚举集合中的所有子集.我们从一个长度的子集开始,然后添加到它们.当我们拥有所有独特的子集时,它们形成一个数组,我们只是按照Horowitz/Sahni中使用的方式迭代它们.

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

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

通过以这种方式删除重复的子集,我们不必将重复项与集合的其余部分保持组合,也不必继续检查它们是否存在冲突,也不必对它们求和.最重要的是,通过不创建非唯一的新子集,我们不会从它们生成新的子集,我相信,这可以将算法从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}但是owait!它已经在阵列中了.这意味着我们现在不向已经有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完全版本的子集求和仅解决容易(多项式时间)问题的地方:

[当我们添加额外元素时,[假设正数之和]以线性速率增长.

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

因此,如果N和P具有相同的顺序,则问题最困难.

如果您假设N和P具有相同的顺序,那么当您添加更多元素时,您无法假设总和无限增长.当您向集合中添加更多元素时,这些元素也需要变大,以确保问题仍然难以解决.

如果P(位置数的数量)是一个小的固定数,那么有动态编程算法可以精确地解决它.

您已重新发现其中一种算法.这是一项很好的工作,但它不是新的东西,也不能证明P = NP.抱歉!

Answer 2

死MG,

你发布已经差不多半年了,但无论如何我都会回答.

Mark Byers写了大部分应该写的内容.

该算法是已知的.

这种算法被称为生成函数算法或简称为动态编程算法.

你的算法有非常重要的特征,即所谓的伪多项式复杂性.

传统的复杂性是问题规模的函数.就传统复杂性而言,您的算法具有O(2 ^ n)悲观复杂度(对于数字1,2,4,...如前所述)

算法算法的复杂性可以表示为问题大小和问题中某些数字大小的函数.对于你的算法,它将类似于O(nw),其中w是不同总和的数量.

这是伪多项式的复杂性.这是一个非常重要的功能.尽管存在问题复杂性类,但这些算法可以解决许多现实问题实例.

Horowitz和Sahni算法具有悲观​​的复杂度O(2 ^ N/2).这不比你的算法好两倍,但是比你的算法好2~N/2倍.Greg可能意味着Horowitz和Sahni算法可以解决问题的两倍大的问题(在子集总和中有两倍的数字)

这在理论上是正确的,但在实践中,Horowitz和Sahni可以解决(在家用计算机上)具有大约60个数字的实例,而类似于您的算法可以处理具有1000个数字的实例(假设数字本身并不太大)

事实上,这两种算法甚至可以混合使用,这类似于Horowitz和Sahni算法.这种解具有伪多项式复杂性和O(2 ^ n/2)的悲观复杂性.

训练有素的计算机科学家可以通过生成函数理论来构建这样的算法.

受过训练和未受过训练的人都可以按照你的方式思考.

不一定用"它是否已知？"来思考.你可以自己发明这样的算法对你很重要.这意味着您可能可以自己发明其他重要的算法,并且有一天可能会发现一个未知的算法.了解该领域的当前进展以及文献中的内容有所帮助.否则你将继续重新发明轮子.

当我回到高中时,我重新设计了Dijkstra算法.我的版本有很复杂,因为我对数据结构一无所知.无论如何,我仍为自己感到骄傲.

如果你还在学习注重生成函数理论.

您可能还想查看维基:

伪多项式时间弱NP-完全强NP完全生成函数

Megli