An Empirical Evaluation of Algorithms for solving Subset Sum Problem in terms of Total Bit Length

Abstract

Subset Sum Problem is an important decision problem in complexity theory and cryptography. Subset sum problem can simply be described as: given a set of positive integers S and a target sum t, is there a subset of S whose sum is t? The complexity of subset sum can be viewed as depending on two parameters: n , the number of values, and m, the precision of the problem (number of bits required to state the problem). Backtracking algorithm for Subset Sum Problem can be modeled as a binary tree where each node represents a single activation of the recursive code. The worst-case time complexity is O(2 n ) when n is used as the complexity parameter [7]. Dynamic Programming breaks a problem down into smaller problems and solves them recursively as divide-and-conquer technique. It solves the problem in O(m.n 2 ) time. Dynamic Dynamic Programming is the extension of the Dynamic Programming with a dynamically allocated list of target sums. It has the time complexity of 2 O(x) when the total bit length x of the input set is used as the complexity parameter.

The empirical analysis shows that time complexity of DP and DDP increase sub-exponentially when bit length, m, is increased by 1. At the same time BT is not sensitive to m and its time complexity increases exponentially when number of inputs, n, is increased by 1.

Keywords: Subset Sum Problem, Backtracking, Dynamic Programming, Dynamic Dynamic Programming, Total Bit Length