Springe direkt zu Inhalt

Rui Zhao:

Exponential Algorithms and Time-Space Tradeoffs for Subset Sum Problem


The Subset Sum Problem is a well-known NP-complete problem. It is both theoretically interesting and practically important to look into it. A very intuitive algorithm is exhaustive search, with time complexity O*(2n) and space complexity O*(n), where O*(.) notation suppresses all polynomially bounded factors. In 1974 Horowitz and Sahni discovered algorithm with time and space complexity O*(2n/2). Then the space complexity was further improved in a classic paper by Schroeppel and Shamir in 1981, and their algorithm is a general-purpose algorithm that can solve a number of NP-complete problems in time T = O*(2n/2) and space S = O*(2n/4), including Knapsack problem. And the Schroeppel-Shamir time-space tradeoff T·S ∈ O*(2n) has long been the most efficient way to trade space against time for the Subset Sum problem. Based on Dinur et al.’s dissection algorithm(2012), in 2013, Per Austrin et al. presented a significantly improved time-space tradeoff curve which matches the Schroeppel–Shamir tradeoff at the extreme points S = O*(1) and S = O*(2n/4) but is strictly better in between and removed strong randomness assumptions.

Bachelor of Science (B.Sc.)