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). The 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
An Empirical Evaluation of Algorithms for Solving Subset Sum Problem in Terms of Total Bit Length GET MORE COMPUTER SCIENCE PROJECT TOPICS AND MATERIALS
