Alladi Ramakrishnan Hall
Small Space Subset Sum Solutions
Sanjay Seetharaman
IMSc
We consider the Subset Sum problem: given a multiset of n positive integers W and an integer t, determine if there is a subset of W with sum t. The problem is NP-Complete: there is no known polynomial-time algorithm. There are well-known algorithms that solve it in either exponential time or pseudopolynomial time and space. The goal of this thesis is to study some techniques that solve it in pseudopolynomial time and polynomial space.
(This will be Sanjay's MSc thesis defence.)
Done