文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Improved low-density subset sum algorithms
侵权投诉

Improved low-density subset sum algorithms

The general subset sum problem is NP-complete. However, there are two algorithms, one due to Brickell and the other to Lagarias and Odlyzko, which in polynomial time solve almost all subset sum problems of sufficiently low density. Both methods rely on bas

Finding short vectors in lattices may be very hard in general. On the other hand, published algorithms, such as the L one, perform much better in practice than is guaranteed by their worst case bounds, especially when they are modi ed 11, 12, 17], and new algorithms are being invented 18, 19, 20]. Thus it is possible that on average, the proble

m of nding short vectors in lattices is easy, even if it is hard in the worst case. Therefore it seems worthwhile to separate the issues of e ciency of lattice basis reduction algorithms from the question of how well the subset sum problem can be reduced to that of nding a short vector in a lattice. (Note that Paz and Schnorr 16] have shown that the general problem of nding the shortest non-zero vector in a lattice is reducible to that of solving some subset sum problem, but with some loss of e ciency.) Consider a lattice oracle that, given a basis for a lattice, with high probability yields in polynomial time the shortest non-zero vector in that lattice. We do not know how to construct such an oracle, but it might be possible to do so, and in any case in relatively low dimensions, known polynomial time algorithms act like such an oracle. The analysis of 11] showed that availability of such an oracle would let the Lagarias-Odlyzko algorithm solve almost all subset sum problems of density< 0:6463:::, but not higher than that. (Similar analyses are not available for the Brickell algorithm 1], although it seems to require even lower densities. See also 8].) In this note we analyze a simple modi cation of the part of the Lagarias-Odlyzko algorithm that reduces the subset sum problem to a short vector in a lattice problem. We show that with this modi cation, a single call to a lattice oracle would lead to polynomial time solutions of almost all problems of density< 0:9408::: . Empirical tests show that this modi cation also leads to dramatic improvement in the performance of practical algorithms. We present some results on this in Section 4. More data and fuller comparisons will be given in 12]. In Section 2 we derive the Lagarias-Odlyzko bound using the approach in 7]. We show in Section 3 that this bound may be increased to 0:9408::: using a simple modi cation of the Lagarias-Odlyzko attack. Finally, Section 4 discusses possible improvements on the new bound and practical results. 3

2. Previous results In 11], Lagarias and Odlyzko show that if the density is bounded by 0:6463:::, the lattice oracle is guaranteed to nd the solution vector with high probability. This

上一页第12页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email