A note on the density of the multiple subset sum problems
Y Pan, F Zhang - Cryptology ePrint Archive, 2011 - eprint.iacr.org
Y Pan, F Zhang
Cryptology ePrint Archive, 2011•eprint.iacr.orgIt is well known that the general subset sum problem is NP-complete. However, almost all
subset sum problems with density less than $0.9408\ldots $ can be solved in polynomial
time with an oracle that can find the shortest vector in a special lattice. In this paper, we give
a similar result for the multiple subset sum problems which has $ k $ subset sum problems
with the same solution. Some extended versions of the multiple subset sum problems are
also considered. In addition, a modified lattice is involved to make the analysis much simpler …
subset sum problems with density less than $0.9408\ldots $ can be solved in polynomial
time with an oracle that can find the shortest vector in a special lattice. In this paper, we give
a similar result for the multiple subset sum problems which has $ k $ subset sum problems
with the same solution. Some extended versions of the multiple subset sum problems are
also considered. In addition, a modified lattice is involved to make the analysis much simpler …
Abstract
It is well known that the general subset sum problem is NP-complete. However, almost all subset sum problems with density less than can be solved in polynomial time with an oracle that can find the shortest vector in a special lattice. In this paper, we give a similar result for the multiple subset sum problems which has subset sum problems with the same solution. Some extended versions of the multiple subset sum problems are also considered. In addition, a modified lattice is involved to make the analysis much simpler than before.
eprint.iacr.org
Showing the best result for this search. See all results