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.)