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
Theorem. Let A be a positive integer, and let a;:::; an be random integers with 0< ai A for 1 i n. Let e= (e;:::; en) 2 f0; 1gn be arbitrary, and let 1
to a lattice oracle.
s= n eiai. If the density d< 0:9408:::, then the subset sum problem de ned by i a;:::; an and s may\almost always" be solved in polynomial time with a single call P=1 1
1
above, A is a xed positive integer and a;:::; an are random integers with 0< ai A for 1 i n. Le
t e= (e;:::; en) 2 f0; 1gn be xed, let s= n eiai, and let i n a . Vectors b;:::; b are de ned as in Section 2. Vector b t= i i 1 n n 1 is replaced, however, by 1 P 1 P=1+=1
Proof. We need to make only minor changes to the proof presented in Section 2. As
b0n 1= (;;:::;; Ns): + 1 2 1 2 1 2
Let L0 be the lattice spanned by the vectors b1;:::; bn; b0n 1. In Section 2, we knew that the vector^= (e;:::; en; 0) was in the lattice L. e 0 does not contain^ but instead contains the vector^0: Notice that the new lattice L e e + 1
^0= (e0;:::; e0n; 0); where e0i= ei?: e 1 1 2
Since ei 2 f0; 1g for 1 i n, we know that e0i 2 f?; g for 1 i n. Notice that k^0k n independent of the number of ei's which are equal to 1. e Again, we are interested in the number of vectors x which satisfy conditions similar^ to Equation 4: 1 2 1 2 2 1 4
^ Setting N> n implies that xn= 0 for any x which satis es Equation 12. Suppose that x= n yibi+ yb0n 1 satis es Equation 12, then we can express xi in^ i terms of yi and y in the following way 1 2+1 P=1+
p
kxk k^0k;^ e x^ 2 L0; x^ 62 f0;^0;?^0g: e e
(12)
xi= yi+ y; for 1 i n; 0= xn= N +1 1 2 ( X
n
i=1
aiyi+ ys:
)
This implies that
X
n
i=1
aiyi=?ys:
暂无评价 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 ...
热门文档