Subset Sum in Time 2^n/2 / poly(n)
share
A major goal in the area of exact exponential algorithms is to give an algorithm for the (worst-case) n-input Subset Sum problem that runs in time 2^(1/2 - c)n for some constant c>0. In this paper we give a Subset Sum algorithm with worst-case running time O(2^n/2· n^-γ) for a constant γ > 0.5023 in standard word RAM or circuit RAM models. To the best of our knowledge, this is the first improvement on the classical “meet-in-the-middle” algorithm for worst-case Subset Sum, due to Horowitz and Sahni, which can be implemented in time O(2^n/2) in these memory models. Our algorithm combines a number of different techniques, including the “representation method” introduced by Howgrave-Graham and Joux and subsequent adaptations of the method in Austrin, Kaski, Koivisto, and Nederlof, and Nederlof and Wegrzycki, and “bit-packing” techniques used in the work of Baran, Demaine, and Patrascu on subquadratic algorithms for 3SUM.
READ FULL TEXT