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
1. Introduction The knapsack or subset sum problem is to nd, given positive integers a;:::; an (the weights) and s, some subset of the ai that sum to s, or equivalently to nd variables e;:::; en, with ei 2 f0; 1g, such that 1 1 X
n
i=1
eiai= s:
(1)
This problem is known to be NP-complete 9] (in its feasibility recognition form), and so is thought to be very hard in general. This has led to the invention of several public-key cryptosystems based on the knapsack problem. Almost all of these have been broken by now, however. (See 2, 3, 5, 15] for surveys of this eld.) Most of the attacks exploited speci c constructions of the relevant cryptosystems. In addition, two algorithms have been proposed, one by Brickell 1] and the other by Lagarias and Odlyzko 11] w
hich show that almost all low-density subset sum problems can be solved in polynomial time. The density of a set of weights a;:::; an is de ned by 1
n d= log max a: i n i 2 1
(2)
The interesting case is d 1, since for d> 1 there will in general be many subsets of weights with the same sum, and so such sets of weights could not be used for transmitting information. The Brickell and Lagarias-Odlyzko algorithms solve almost all subset sum problems with d su ciently small. Both the Brickell and Lagarias-Odlyzko algorithms reduce the subset sum problem to that of nding a short vector in a lattice. The exact complexity of nding short vectors in lattices is not known, and expert opinion appears to be divided as to whether this problem is polynomial or not. At the moment, the best known polynomial time method in this area is the L lattice basis reduction algorithm of Lenstra, Lenstra, and Lovasz 13], which is only guaranteed to nd a non-zero vector in an n-dimensional lattice that is at most an exponential times the length of the shortest non-zero vector in that lattice. If one uses that algorithm, the Lagarias-Odlyzko method can be shown rigorously to solve almost all subset sum problems of density< c=n for large n and for a xed constant c, as is done in 11]. (See 7] for a simpli ed analysis of the algorithm.) Using more recent algorithms of Schnorr 19], one can improve the cuto bound to c0=n for arbitrarily small constants c0> 0, but at the cost of increasing the degree of the polynomial that bounds the running time. 3
暂无评价 14页 免费 Improved low-density sub... 暂无评价 18页 免费搜...Branching proofs of infeasibility in low density subset sum problems G?bor ...
M. Odlyzko, “Solving low-density Subset Sum problems“, J. Assoc. Comp...Euchner M., “Lattice Basis Reduction: Improved Practical Algorithms and ...
M. Odlyzko, “Solving low-density Subset Sum problems“, J. Assoc. Comp...Euchner M., “Lattice Basis Reduction: Improved Practical Algorithms and ...
Improved low-density subset sum algorithms[J]. Computational Complexity,1992,2(2): 111-128. [11] 于志强, 罗世新, 徐树民等.对一个公钥密码体制的格...
subset_sum_problem_计算机软件及应用_IT/计算机_专业资料。CS 105: Algorithms (Grad) Subset Sum Problem Soumendra Nanda March 2, 2005 1 What is the Subset...
improved low ? density subset sum algorithms[j]. computational complexity, 1992, 2(2): 111-128. ?[3] odlyzko a m. the rise and fall of knapsack ...
Stern. Improved Low-density Subset Sum Algorithms. Computational Complexity, 2:111–128, 1992. CosterLaMacchiaOdlyzkoea:91 . . . . . . . . . . ....
7页 免费 Improved low-density sub... 暂无评价 14页 免费喜欢此文档的还喜欢...Subset-sum Problem- and other balanced knapsack algorithms An O(nr) algori...
Improved low-density sub... 暂无评价 14页 免费 Improved low-density sub....algorithm for the Subset-sum Problem and other balanced knapsack algorithms ...
Afterwards, similar problems turned up in -4- connection with an algorithm for solving low-density subset-sum problems [9], where a crucial role in ...
热门文档