In the Equal-Subset-Sum problem, we are given a set @math of @math integers and the problem is to decide if there exist two disjoint nonempty subsets @math , whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in @math time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give @math worst case Monte Carlo algorithm. This answers the open problem from Woeginger's inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in @math time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in @math time and polynomial space.
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 basis reduction algorithms to find short non-zero vectors in special lattices. The Lagarias-Odlyzko algorithm would solve almost all subset sum problems of density<0.6463 ... in polynomial time if it could invoke a polynomial-time algorithm for finding the shortest non-zero vector in a lattice. This paper presents two modifications of that algorithm, either one of which would solve almost all problems of density<0.9408 ... if it could find shortest non-zero vectors in lattices. These modifications also yield dramatic improvements in practice when they are combined with known lattice basis reduction algorithms. The subset sum problem is to decide whether or not the 0-l integer programming problem S n i=l a i x i = M , ∀I , x I = 0 or 1, has a solution, where the a i and M are given positive integers. This problem is NP-complete, and the difficulty of solving it is the basis of public-key cryptosystems of knapsack type. An algorithm is proposed that searches for a solution when given an instance of the subset sum problem. This algorithm always halts in polynomial time but does not always find a solution when one exists. It converts the problem to one of finding a particular short vector v in a lattice, and then uses a lattice basis reduction algorithm due to A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovasz to attempt to find v. The performance of the proposed algorithm is analyzed. Let the density d of a subset sum problem be defined by d = n log 2 (max i a i ). Then for “almost all” problems of density d d n , it is proved that the lattice basis reduction algorithm locates v. Extensive computational tests of the algorithm suggest that it works for densities d d c ( n ), where d c ( n ) is a cutoff value that is substantially larger than 1 n . This method gives a polynomial time attack on knapsack public-key cryptosystems that can be expected to break them if they transmit information at rates below d c ( n ), as n → ∞. The Merkle-Hellman cryptosystem is one of the two major public-key cryptosystems proposed so far. It is shown that the basic variant of this cryptosystem, in which the elements of the public key are modular multiples of a superincreasing sequence, is breakable in polynomial time.